I immediately remembered about this story too. This is pretty hilarious:

"Containing a Harry Potter book, the letter was sent to a Russian student by her French friend, who manually transcribed the address that he had received by e-mail. The Frenchman's e-mail program was not set up correctly, so the Cyrillic characters encoded as KOI8-R were instead displayed as diacritic symbols from the Western character set (ISO-8859-1). Russian postal employees deciphered the address and delivered the package successfully."

Either that, or they've spent so much time on the pre-Unicode Internet that they can sight-read Cyrillic characters encoded as Latin-1...

Maybe the Russian postal service has a good crypto team as a remnant of the soviet era.