Выясняется, что билет в оба конца (Республика Алтай) на автовокзале (г. Барнаул) нельзя взять...
И как выбираться обратно...

А на Новосибирском автовокзале такая же ситуация?
Туда билет взял, уехал- хорошо.... а обратно- как повезет... Будешь на дороге куковать....

хм, вообще кроме автобусов вроде как от Барнаула до Горно-Алтайска курсируют маршрутки (кстати, я дважды выезжал из вашего города и оба раза у транспортного средства колеса пробивало)))) Можно попробовать пойти в какую-нить турфирму и спросить там билет на их автобус, если места свободные будут - вас возьмут с собой и туда и обратно.