Kosh Agach to Khandagayty
I failed in November 1998! I was (mostly) hitching around the world then.
I visited the mountaineering association in Gorny Altai who gave me an excellent map and said I should get a border zone pass in K A. I took the bus (what a landscape!) and found the 'hotel', 2 very simple rooms, earth closet behind the shop nearby and it got warm by morning, when cold water was brought to wash from a tin basin in the corridor. Cost 1 dollar.
Next day I applied at the local military base (helpful and friendly), but the superior officer with authority was - visiting the M. A. in G-A!!! (perhaps they had told him I was coming and he wanted to discuss it with them). So I was told to come back next day for his reply by radio, and to get a hot shower - my first in the Republic of Altai as the hotel in G-A had no water.
The answer was no, due to 3m snow and high winds on the passes, their own patrols were then cancelled. The officers spent their time playing simple computer games like tetris. I was invited to return during better conditions when I could if I wished join one of their patrols! Now I am sure it is very different under Putin. His FSB (ex KGB) has been given sole control over all the widened border zones.
However, I got to Tyva through Russia - getting there by hitching the back road from the Republic of Khakassia. I got arrested by the young Tyvan internal border guards who had never seen a business visa (the most flexible for travelling then) and had no comms or transport. After a sleepless night in their hovel they sent me in a passing truck to Ak Davorak, where I got a formal official apology - eventually, after threatening an international diplomatic incident. On arrival in Kyzyl I went as always to the English dept at the uni, where I ended up with a job and stayed 2 years!!!
I did actually get around the world with my thumb, rucksack and tent - and a young Tyvan lady!
After that I went to the Republic of Kalmykia, also Mongol Buddhist but in Europe, and also taught for 2 years, got involved in pro-democracy activity, threatened with up to 4 years in prison and now can't get a visa. My partner is a Kalmyk though, so I have an excellent souvenir!
Best wishes - get in touch if you think I can offer any useful info.