Just to be clear: Doom was legal to buy, own and play before if you are over 18. Now it's free to put up ads for it and sell it openly.
There are two ways a game can be indexed in Germany.
The one is the index list Doom was on.
They can't be sold in the open, but they can on demand to persons over 18.
The second is when games get 'beschlagnahmt', confiscated.
Then the games are actually illegal to sell at all and illegal to own.
Games like Wolfenstein 3D, The Darkness and Dead Rising are confiscated, at least the uncut versions.
However, even the 'normal' index poses a big problem for big retailers like Media Markt (like Best Buy, I guess) because they can't put up ads for indexed games and can't put them on the shelves.
They generally do not sell or import games in demand. Small gamestores tend to do that, though.
Steam is too lazy or incompetent to implement a working age-check, so they just ban all germans from buying certain games.
/edit:
Also, most 'Indizierungen' happen because of violence, 'Beschlagnahmungen' because of Nazi-symbolics. Although excessive violence can get a game the 'confiscated' status, like Manhunt, Mortal Combat, Soldier of Fortune...