SimonG: "Banned", for the most part, just means that the game can not be sold or adverstized to minors. You could buy Quake in Germany since its release. same for Doom, etc.
It's more a marketing thing, like a M or PG rating in the US.
"Illegal" games, like "Wolfenstein" can and never will be sold in Germany. Several things can make a game illegal (extreme violence e.g.), but showing symbols of the Nazi reign are pretty much the safest way to make a game illegal. In some extreme cases, even private ownership is considered a crime, but "normally" online disrtebution is punishabel by criminal law.
Wolfenstein 3d is illegal because it "glorifies" Nazis. By killing them, don't ask me ...
"Banned" games get reevaluated at regular interwalls. River Raid was once banned. And Desert Strike was banned for glorifying the Gulf War. Rather tame titles today...
IMO the German gov't should be kicked in the nuts for trying to sweep their past under the rug via banning Nazi games/references. I get trying to discourage neo-nazism and all, but banning Nazi themed games is imo a step too far.