I asked my friend and it turned out that I was partly wrong. The stamp in question is not "for permanent residence abroad" (these stamps were abolished indeed quite a time ago) but "consular registration". He says he was issued a passport with a stamp like this even though he'd never explicitly registered with the consulate.

I found a sample of this stamp on the internet:

("Принят на учёт в Консульском отделе Посольства России в Чешской Республике" = "Registered in the Consular section of the Embassy of Russia in the Czech Republic").

Once you have this stamp in your passport for traveling abroad, it becomes the primary identification document for you (and then you don't need an internal passport).