I am trying to come up with some search heuristics for Russian first names and it would speed up the process if I could eliminate searching through certain names. There's obvious letters that could I can skip (Q, X) but being able to skip more common letters would speed things up. Would I miss any major names by skipping C? Any other good letters to skip?
Short answer: normally transliterated Russian names cannot start with
Long answer: sometimes the name bearer can change that.
There is a law (Приложение N 6 к Приказу ФМС от 26.03.2014 N 211) that explicitly states how Cyrillic names should be transliterated in Russian-issued foreign passports. However, it also states that applicant may have their name registered in other transliteration variant if they provide an official document (e.g. a passport issued under older rules, by foreign country's authority etc).
Also some people prefer to use more "westernized" variants of their names (especially in social networks):
Константин → Constantin (instead of Konstantin)
Клавдия → Claudia (instead of Klavdiya)
Клара → Clara (instead of Klara)
This may also apply to foreign citizens of Russian descent, a notable example is Russian-Estonian Климент Иванов (Clement Ivanov).
C aside, there are also other interesting cases. Famous boxer Владимир Кличко spent most of his career in Germany and was promoted there, so he choose his name to be written in German translit: Wladimir Wladimirowitsch Klitschko. This variant passed on into all official sources. A counterexample is another famous boxer Костя Цзю, known internationally as Kostya Tszyu, which is closer to traditional Latin translitertion of Russian. As he is of Korean descent, he may have chosen to be written Ju (주) but obviously preferred not to.
Well, the majority of Russian names have Greek or Jewish origin, but well, that is the state of things for centuries, so let consider them Russian. In that case, there's at least one common Russian name (originally Greek),
Кирилл, which is usually transliterated with 'C' - Cyril. While it can be transliterated also as Kirill, Kiryl, Kirillos, Kyrylo, Kiril - the C-form is the most accepted.
So, to answer your question, you'll miss at least one popular name.
UPD: @SomeWittyUsername has a very reasonable point that Cyril can be treated rather as a corresponding western name rather than a transliteration. Well, I tend to agree. If you take some modern Russian celebrity, you'll see that it's most likely will referred as Kirill -
- but! - however, you'll still encounter Cyril form a lot. It's a bit tricky to tell apart "real" transliteration and the forms constantly used. Since the question is about not missing somebody Russian in some non-Russian language list -
Cyril still should be kept in mind.
Also, historical figures of Russian origin are usually still referred with C-form.
As for other letters for skipping - H (with the same exclusion of Western correlates - Genrikh/Henry, etc.), and W (again, Vilyam/Uilyam/William can be an exclusion, but then, it's not quite a major Russian name anyway). Russian words with Cyrillic Х are to be given with Kh not H (Khariton, Khruschev, etc.).
I recall the name of writer Константин Паустовский being transliterated as Constantin Paustovsky.