You could try this for variations of names. http://kurufin.ru/html/Greek/greek_names_h.html
I found my family in Odessa. I had been looking for them from Moscow, but although they did go to Moscow where other children were born, the originated in Odessa and the Crimea is where the Greeks lived.
Try that site for name variations.
Mighthelp is great with suggestions. If they were Greek they would have records at Greek or Russian Orthodox churches otherwise there are the other churches. My family were Greek and then went to Russian Orthodox church once in Moscow.