AFAICT Gears of War was not banned but rather not allowed to be sold OR ADVERTISED to minors as is/was the case with most "violent" games. Only a few (e.g. the uncut version of Left 4 Dead) were ever banned from sale entirely. Of course the distinction is mostly theoretical as no store is willing to sell either games even with age verification.

That's not quite true. You are allowed to buy games without an age rating in Germany, if you are over 18. However, the burden is onto the seller to verify your age and it might not be publicly listed. So many resellers are not bothering importing games under these conditions, but they would be allowed to.

The same is true for Quake 3 Arena. They didn't meet the requirements for USK-18 (similar to pegi) at the time.

But I don't think that's a thing anymore because there outdated policys have changed. Video games aren't "new" anymore for a long time.