Только что посмотрела сайт посольства в Китае, там из стран СНГ только граждане Казахстана могут находится до 90 дней без визы на тер Монголии.
kisha, если Вы точно не уверены, что поставят на границе визу, может быть Вам поступить проще, договориться с какимнибудь тур агенством, отправить им паспорта по экспресс почте, они сделают визы и также отправят Вам.