проверяют ли на границе белоруссия-украина факт прохождения военной службы

Это НИГДЕ не проверяют. Пограничники проверяют, не находится ли гражданин в списке лиц, которым запрещен выезд за рубеж, а попасть в этот список человек может, в том числе, и по милости министерства обороны, если он объявлен в розыск как злостный уклонист. А погранцам по-барабану, как и почему Вы в этот список попали...