Each book for system users (not even power users!) had a chapter about different character sets and common problems like this. This was important.
I think the post office worker was enough of a geek or they took the package to the computer guy.
Still more interesting thing to me was that the sender got the address in the wrong encoding and instead of asking via email, just must have thought that Russians have their little ways and dutifully copied all the gibberish (Russians even have a specific term for misencoded characters: krakozyabras).
First they knew Russia, Moscow by the postcode, so they superscripted РОССИЯ МОСКВА, and then they knew which garbled letters correspond to these ones
After which they were able to decipher ПР Р.А.СКО.О
after which the address becomes obvious (with the help of index) that it is Проспект Вернадского, 37. I don't think they used any tables other that this implicit table.
Which is student dormitory of Moscow State University btw, I looked it up.
Wow, I want to know more about how the postal worker who deciphered it! On a computer, sure just convert it. But on paper, how did they work it out?