The mistake in your reasoning is to conclude that, since the net flux through a closed surface is zero then the electric field everywhere on that surface, and in space, should be zero. This is not true. Since flux contains the dot product of the vector field with the local normal to the surface the field could have some + flux at points and - flux elsewhere on the surface. It is entirely possible for the field lines to cut the the surface in both directions (inside to outside) and (outside to inside) leading to a zero for the sum.
In the case of the dipole you have a + and a - charge of the same magnitude, Q, and you have field lines that leave the +Q and land on the -Q. If you just draw the picture and sketch some field lines you will see that when you draw a circle around both charges as many lines go into it as out of it, therefore ZERO flux over all. Your sketch better be accurate.
Gauss' Law states that the total flux through any closed surface id proportional to the net charge enclosed within that surface, Flux ~ Q_inside. You cannot use this to evaluate the electric field on the surface except in situations with a high degree of symmetry and that might be causing confusion. Many texts use Gauss' law to calculate the Electric field due to a uniform spherical charge distribution or an infinite line of charge. In such cases you are justified making the claim that E is constant on the surface (a surface that respects the symmetry of the source) and puling it our of the flux integral. For the dipole you cannot do this. The fact that Flux = 0 when E != 0 is not a contradiction in this example.