Gauss's law is always fine. It is one of the tenets of electromagnetism, as one of Maxwell's equations, and as far as we can tell they always agree with experiment.
The problem you've uncovered is simply that "a uniform charge density of infinite extent" is not actually physically possible, and it turns out that (i) it is not possible to express it as the limit of a sequence of sensible physical situations, and (ii) it is not possible to provide a proper mathematical formalization for it. It's a bit of a bummer, because you can do this perfectly with infinite line and surface charges, but bulk charges just don't work like this.
This might seem a bit strange (and, really, it should), so let's take another look at what you mean when you say "space is filled" with charge of density $\rho$. Could you implement this in real life? Of course not! You can only fill up some finite volume $V$. Your hope then is that as $V$ gets bigger and bigger, the field inside it stabilizes to some sort of limit.
The problem is that for this procedure to make sense, you need the limiting procedure to be independent of the detailed shape of $V$ as you scale it up, for surely if you're in the centre of the slab and the field has mostly converged, the answer can't depend on details of a boundary that's very far away.
For a line and a surface charge, this works perfectly. You can calculate the field for a finite line charge, and the limit doesn't depend on which end goes to infinity faster as long as they both do. You can also prove that the field of increasing patches of surface charge does not depend too much on the shape of the patches if they are big enough. For bulk charges, though, you've just proved that it doesn't work: if you displace $V$, you get a different answer. Hence, the problem for an infinite spread of bulk charge doesn't make sense, and it's not the limit of sensible physical systems that are "big enough".
Another way of showing that the "big enough" property doesn't make sense is that there is nothing to compare the charge's size with. For line and surface charges, this is perfectly fine, and in fact all they are is models for a finite line / surface charge of length / radius $L$, whose field is tested at a point a distance $d$ from the charge. The distribution is "infinite" if $L/d\gg 1$, or in other words the models are good if the point is much nearer to the source than the source's size. For a bulk charge, there's no meaningful distance $d$, and hence no meaningful dimensionless parameter to take a limit over, and this in turn is what drives the meaninglessness of the situation.
Finally, let me put this a bit more mathematically, in a way that sort of makes it have an answer. Another way to phrase the problem "space is filled with a uniform bulk charge of density $\rho_0$" is as the simple differential equation
$$\nabla\cdot \mathbf E=\rho_0/\epsilon_0.$$
This is a perfectly reasonable question to ask, except that you're missing boundary conditions, so the solution won't be (anywhere near) unique. However, boundary conditions don't make sense if your domain is all of space, so you need something else, and what turns out to do the job is to demand answers which share the symmetry properties of the charge - both the translation symmetries and all the point symmetries.
For line and surface charges, this actually works almost perfectly. The coupled symmetry and differential equation demands have, fortunately, unique solutions: the translation symmetries and the differential equation rule out everything except uniform fields, which are then ruled out by the point symmetries.
For a bulk charge, on the other hand, you get a fundamental linear dependence and a uniform field, which cannot be ruled out by the translational symmetry:
$$\mathbf E=\frac{\rho_0}{3\epsilon_0}\mathbf r + \mathbf E_0=\frac{\rho_0}{3\epsilon_0}(\mathbf r-\mathbf r_0).$$
This form is sort of translation invariant, except that now you have to re-choose $\mathbf r_0$ every time you translate, which can't be quite right. And if you try to impose any point symmetries, you'll need to put $\mathbf r_0$ at every point with an inversion symmetry - and there you lose out, because it cannot be done.
To rephrase this last bit in your terms, the inversion symmetry requires that the field be zero at every point, but this is not consistent with the differential equation. You always have "infinitesimal" bits of charge at $\vec r$ and $-\vec r$ producing infinitesimal bits of field which cancel each other out, so the field should be zero at every point. This is indeed inconsistent with Gauss's law - but you can simply chalk it up to the fact that the problem is inconsistent.