Здравствуйте. Все верно, в действующем законодательстве не указан перечень подтверждающих документов пребывания в другой стране.
То есть они могут быть совершенно различными: билет на самолёт/поезд; визу; договор аренды жилья за рубежом; договор об обучении или трудоустройстве за рубежом итд.
Для того, чтобы сняться с воинского учета необходимо подать заявление о снятии с воинского учета, так же принести приписное удостоверение (они его изымут) и все подтверждающие документы, которые у вас имеются.
Лучше сниматься с воинского учета в не призывное время, тогда меньше всего возникает вопросов со стороны военкомата.
Так же будете готовы рассказать, чем будете заниматься заграницей, на сколько уезжаете и как правило по мимо билета на самолёт просят дополнительно иной подтверждающий документ.
Если не ошибаюсь на счёт вида на жительства - порой его можно сделать, только находясь уже в другой стране, поэтому требовать у вас они его не могут.