So I thought I'd drop a line about all this ... in case someone in my situation needs answers. I made it to Moscow and, as I was crossing the passport control, asked the guy in the booth whether he would let me out of the country with that stamp in my passport. He said he didn't care about the stamp. He even added that he didn't understand why it could possibly be an issue.
For my part, it appears that I will have the stamp cancelled before I have to leave Russia. But his words seemed reassuring.
Out of curiosity, how would you go about canceling that particular stamp? The office that takes care of the internal passports? Is that the local branch of the MVD?