Using Gauss's law when point charges lie exactly on the Gaussian surface

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.

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.

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