Russian, itself, lends to a lot of confusion when names are transliterated to Roman characters - for instance, the following. Note that the character "й" may be used for "j" or "y" (in most cases). The same goes for "я", which can be written "ja" or "ya". Most other Eastern European languages pronounce "j" as the leading "y" sound as well.
Мария
Transliterates directly to: M-a-r-i-ya or M-a-r-i-ja in some forms. The Romance spelling of the same pronunciation is Maria.
Алексей
Transliterates directly to Aleksei, Aleksey or Aleksej. The most common spelling of the "ks" sound in English languages is "x", which Russian does not have. Therefore, the standard Roman-character spelling is Alexei.
I think Anastasia's name has been examined pretty thoroughly enough by Leah already, so I won't do that.
However, there are a lot of unexplained instances of language muddling, especially with surnames. For example, Peter Ilych Tchaikovsky (his middle name's a good example of the use of "y" as an "i" sound, too) has a very well-used last name, but for some reason, people seem to think it's funny or "cool" to spell it in a more exotic manner. Here's all the variations I can recall:
Chaikovsky
Tchaikovskiy/Tchaikovskij (Neither of which is technically incorrect, but the "i" near the end is unneccessary in English)
Tchaikovfsky
Tchaikofsky
Tchaykovski
Etc. and etc.
I could quote a lot more on a lot more names, but...you get the point.
