My theory is that the way Russian names got transliterated basically had to do with whether an obvious English equivalent exists, and whether they were well known among the broad public at a time when the relevant people — that is, those who popularized the person in the English-speaking world — didn't care (as they seem to do now) about keeping the name in the original language.

This explains Nicholas II and Leo Tolstoy, as well as Joseph Stalin if the "ancient" period of not caring is extended to the 1950s. The exception seemed to be Pyotr Ilich Tchaikovsky — whose last name, which we would now spell Chaykovsky or Chaikovsky or Chaikovskii, comes to us from the French, back when Russian musicians were popularized that way. (The French were also into the double-ff instead of v at the same of "-ov" and "-ev" names. See, for instance, the scientist Ilya Mechnikov, also known as Elie Metchnikoff.) So I did a bit of digging in the Library of Congress catalog, where I found items calling Tchaikovsky Peter — a 1880 picture, a 1905 biography, a 1906 English translation of the biography by his son Modeste, and a 1953 "Story of Peter Tchaikowsky." All the stuff from the 1970s and afterward that I've seen with his first name has Pyotr or Piotr. The old versions also have inconsistent last name conventions, from Tchaikowsky to Tchaikovski, which is usual for Russian names back then.

So here's my theory: A Russian first name would naturally have been converted into the English first name if:

1. there's an obvious English equivalent (so no on Fyodor, Ivan, etc.);

2. the person was well known among the masses, not just among people who studied that subject; and

3. the person became known in the 1950s or before.

But the basic idea isn't so much that the English name would stick, but rather that people didn't really care about accuracy. So you might easily have alternate spellings as well as the Russian name. So Peter could have been Piotr or Pyotr then; Stalin could have been Iosef or Josef. (Josef is probably because that's how it often is in Central European languages; and just like with Tchaikowsky, everyone used their own transliteration style, which often consisted of taking a transliteration they had picked up from a different language.)

This leaves one more question: What about names that changed back in the last generation, when people started to care? Why did we go to Pyotr Tchaikovsky but stick with Joseph Stalin? So in the more modern period, I would predict that you'd see the Russian name used almost uniquely, except for people who first became known during the earlier period and are well known enough that their Anglicized name stuck. This threshold may be different than the previous threshold. So Tchaikovsky could have become Peter at the turn of the century and gotten converted to Pyotr; but Stalin and Tolstoy got Anglicized names and were too well entrenched to have gotten converted.

So the two thresholds give us three categories of people: (1) old people who were never converted like Dostoyevsky + new people like Gorbachev, (2) old people who were converted and then converted back, like Tchaikovsky, and (3) old people who were converted and were too far gone to convert back, like Stalin and Tolstoy.

In response to some of the commenters from Eugene's post:

• The "tsar"/"czar" business is again from when people didn't care. "Tsar'" is short for "Tsesar'," that is, "Caesar." (These guys took the title "tsar'" precisely to avoid being kings and instead to proclaim their imperial pretensions.) Even into the 20th century, the Tsar's son was called not just "Tsarevich" but also "Tsesarevich." Anyway, in olden times when people didn't care, "Caesar" to "Csar" to "Czar" is an easy set of hops. As for the German "Kaiser," that's the German form of "Caesar" too, and that's even easier — we're inclined to keep the spelling of something originally written in the Latin alphabet.

• Christopher Columbus and Gustavus Adolphus are from cultures with traditions of Latin forms. Columbus is Latinized just because he's old and folks who wrote about him at that time did so in Latin, same reason we talk about Mercator, Lassus, and Erasmus, as well as city names like Vienna; similarly with Charlemagne, since only Germans would talk about Karl der Grosse, and similarly with Frederick Barbarossa. Swedes seem to have retained this Latinizing tradition into more modern times, which is how we get Linnaeus and Gustavus Adolphus.

• The French have always been more into Gallicizing foreign names — Barberousse, Christophe Colomb, pronouncing "Mozart" without the German "z" sound and with a silent "t", etc. Actually, they used to put the "-us" and similar endings on classical names (just read Montaigne), but sometime between then and now they dropped that. (Same goes with Russians, who used to say "Kolumbus" for Christopher Columbus but now say "Kolumb.") Though note that Leonardo da Vinci is Leonard de Vinci for an additional reason — he also worked in France during his life, and that's how he would actually have been known in France.

• The same theory as for Russians also goes for other nationalities, like why Juan Carlos is Juan Carlos now but Felipe II is still Philip II. If there had been a widely known Spanish king called Juan Carlos in the 17th century, when no one cared about this sort of thing, I would bet he would have been called John Charles.

UPDATE: More on tsar and czar in the comments.