Using Gauss's law when point charges lie exactly on the Gaussian surface Suppose you place a point charge $+Q$ at the corner of an imaginary cube.
Since electric field lines are radial, there is no flux through the three adjacent (adjacent to the charge) sides of the cube. However there is some amount of flux passing through the other three sides of the cube (flowing out of the cube).
We can estimate that the flux through these three surfaces combined is equal to $Q/(8\epsilon)$. As, if you consider $7$ other cubes having the charge at the corner, each of them would have equal flux flowing out by symmetry and since the total flux through the $8$ cubes is $Q/\epsilon$, each cube would have a flux of $Q/(8\epsilon)$.
Now apply Gauss' law to the cube, and we find that the cube encloses a charge of $Q/8$.
This means that 1/8th of the charge belongs to this cube. 
But the charge we placed was a point charge with no dimensions. It cannot be split into parts.
What is wrong?
 A: How do you define a point charge? Let us add some formality to that: Consider a spherical charge of radius $r$ centered at the cube's vertex, with uniform charge density $\rho_v=\frac{3Q}{4\pi r^2}$ (so that the total charge is $Q$ and the electric field is the same as a point charge's at a distance $d > r$). We can define our point charge as the limit of this spherical charge as $r\rightarrow 0$. The amount of charge enclosed by the cube for any $r>0$ is, by the same symmetry argument you used, $Q/8$. so the charge "enclosed" for all purposes of Gauss' law is:
$$Q_{enc} = \lim_{r\rightarrow 0}{\frac{Q}{8}} = \frac{Q}{8}$$ 
Now, why should we use a sphere for the limit and not another shape that could give a different result? That's because only a uniform sphere can replicate the electric field of a unit charge over all space outside its body, no matter the size (radius), and thus converge to a unit charge on the limit for all electrical purposes.
A: Gauss's law applies to situations where there is charge contained within a surface, but it doesn't cover situations where there is a finite amount of charge actually on the surface - in other words, where the charge density has a singularity at a point that lies on the surface. For that, you need the "Generalized Gauss's Theorem" [PDF], which was published in 2011 in the conference proceedings of the Electrostatics Society of America. (I found out about this paper from Wikipedia.)
The Generalized Gauss's Theorem as published in that paper says that
$$\iint_S \vec{E}\cdot\mathrm{d}\vec{A} = \frac{1}{\epsilon_0}\biggl(Q_{\text{enc}} + \frac{1}{2}Q_{\text{con}} + \sum_{i}\frac{\Omega_i}{4\pi}q_{i}\biggr)$$
where


*

*$Q_{\text{enc}}$ is the amount of charge fully enclosed by the surface $S$ and not located on $S$

*$Q_{\text{con}}$ is the amount of charge that lies on the surface $S$ at points where $S$ is smooth

*$q_i$ for each $i$ represents a point charge that is located on $S$ at a point where $S$ is not smooth (i.e. on a corner), and $\Omega_i$ represents the amount of solid angle around that that point charge that is directed into the region enclosed by $S$.


There are a few edge cases (haha) not handled by this formulation (although it should be straightforward to tweak the argument in the paper to cover those), but fortunately it does cover the case you're asking about, where a point charge is located at a corner of a cube. In that case, the amount of solid angle around the corner that is directed into the interior of the cube is $\Omega_0 = \frac{\pi}{2}$. Plugging in that along with $q_0 = Q$ (the magnitude of the charge), you find that
$$\iint_S \vec{E}\cdot\mathrm{d}\vec{A} = \frac{1}{\epsilon_0}\biggl(0 + \frac{1}{2}(0) + \frac{\pi/2}{4\pi}(Q)\biggr) = \frac{Q}{8\epsilon_0}$$
which agrees with what you've found intuitively.
A: Gauss’ law says the net flux through a closed surface equals the net charge enclosed by the surface divided by the electrical permitivity of the space.
I don’t see how a point charge at the corner of a cube can be considered as enclosed by the surfaces of the cube. Gauss’ law applies to a closed surface. The cube minus three surfaces does not constitute a closed surface. Moreover, as @ZeroTheHero points out, it does not make sense to divide a charge having no dimensions into an eighth.
In summary, I see no Gauss’ law paradox.
Hope this helps 
A: Gauss' law requires charges enclosed to be completely enclosed within the volume that you're considering (i.e. the charge must be contained in an open subset in the usual topology of $\mathbb{R}^3$ that is totally inside the compact domain under consideration). If not, you can argue using symmetry considerations. For example if your charge is at the boundary of a smooth surface, it would yield half a solid angle contribution because it's half inside/half outside etc. For a proper argument, imagine a charge at the boundary of a smooth volume, then reflect the volume about the tangent plane and consider the limit of a surface that encloses the union of both these volumes from the outside...by symmetry we would have $Q/\epsilon_0$ flux for both and $Q/2\epsilon_0$ through each.
The generalized divergence theorem in the answer of @DavidZ seems to have generalized this. I wasn't aware of the generalized result, but now it's easy to imagine it would hold for $4\pi/N$ solid angle, if $N$ is an integer - just cover the $4\pi$ solid angle with $N$ of these volumes....from this one can extend to rational fractions of $4\pi$...and then by continuity to all arbitrary solid angles.
In your case, you can imagine enclosing the central charge inside 8 symmetrical cubes joined at the vertex where the point charge resides....then you'd get  $Q/\epsilon_0$ flux through all of them and $Q/8\epsilon_0$ through each of them by symmetry.
