Oh, un autre adepte du train! Cela fait très plaisir ^^
J'allais conseiller l'excellent site donné par Michelem

Je vois qu'elle m'a devancé! Il donne les horaires et toutes les infos utiles. Il existe apparemment deux trains hebdomadaires reliant le Kazakhstan et Urumqi. Il y aurait un train tous les deux jours entre Moscou et les gares casaques en correspondances pour Urumqi, via deux itinéraires. Le site donne les liens pour vérifier les horaires.
Pour ma part je projette de faire le trajet via la Mongolie! Peut-être que je reviendrai par là...

Vive le train!
Ah, j'oubliais. Il existe au moins une voiture directe Paris Est-Moscou. Cette relation a été remise en place en 2007.
Le site des RZD, les chemins de fer russes, donne les horaires et les tarifs:
http://www.eng.rzd.ru/isvp/public/rzdeng?STRUCTURE_ID=4127
Il est également possible de passer par l'Allemagne sans relation directe. Les RZD donnent également les horaires de leurs autres trains internationaux. Un site bien pratique, il est impossible de trouver de tels horaires sur celui de la SNCF!