I forgot to say that the first one to sing the song was a young artist, Vladimir Troshin, in 1958. When Mark Bernes turned it down, Troshin begged Solovyov-Sedoy for it.
Here is Podmoskovnye Vechera in Russian, performed by a much older Troshin.
http://uk.youtube.com/watch?v=CC0wsBzHrzc