Yes Heiko, I have gone a couple of different ways near there. Both as shown on the maps above, and a variation, which was from PetroPavlovskoye (the most northerly point of the shortcut) directly east to Gorno Altaisk. (see red line on this map below)
http://farm7.static.flickr.com/6136/...82d85b0a_o.jpg
From the KZ-RU border between Shemonaikha and Zmeinogorsk (which is quicker and more peaceful than the main highway crossing) to PetroPavlovskoye is pretty much all asphalt, reasonable condition.
If you want to stay on asphalt, then take the red line on the map above, directly east to the main highway. Its not as scenic as the yellow line south of PetroPavlovskoe. Also the red line goes through Russian areas, with mostly Russian people, while the yellow line south of PetroPavlovskoe travels into real Altai territory ... with the Altai people, and Altai villages.
If you take the road south from PetroPavlovskoe to Ust Kan and then back to the main highway, it is mostly dirt road (gravel) from PetroPavlovskoe to Ust Kan, and then asphalt from Ust Kan back to the highway. There are one or two more clayish sections than can get slippery if it has been raining heaviily, but mostly its good gravel. The dirt section is pretty good, and if the weather is good there is no reason you cant ride it at 100 - 120 km/h. I figure if someone is going to Mongolia, there is no point trying to avoid dirt roads.
Note: If you are coming thru KZ from the south (Almaty) then its best to avoid Semey altogether and go direct to Ust Kamenogorsk (Oskemen) and from there to Shemonaikha and the Russian border. There is some short (20-30km) of wide, fast, gravel road between Ust Kamenogorsk (Oskemen) and Shemonaikha, but the rest is asphalt.
