As a blond female the police never even look at me and customs agents usually ignore me. But after the Feb bombing my bags were searched for the first time ever at the airport. They even hand inspected every tiny makeup brush! (terrorists must have come up with a new teeny tiny explosive). And my red haired blue eyed son (100% Russian) was hasseled on a train coming home from the south. I think people who have a darker complexion probably had a lot more problems. I saw them being asked for documents at almost every metro station (same thing happened after the Pushkin station bombing in 2000).
Scare story? Not really. Just part of life when living in a foreign country. In Los Angeles we have daily roundups of illegal aliens by the cops. But if you follow the law and have all your visas and papers legal you won't get picked up.
Same in Russia. If you purposely don't follow the country's laws you run a risk. If a cop asks for documents and you hand him an unregistered or expired visa then you get what you deserve for breaking the law.
It always amazes me how people think they have a right to break Russian visa laws. It isn't hard or any more expensive to enter the country legally and maintain a legal visa than it is to go through all the contortions of doing it illegally.