Что делать, если в военкомате отрицают снятие с учета при наличии уведомления на Госуслугах?

Ситуация действительно запутанная, но решаемая. Я подскажу, как действовать. Сразу оговорюсь: само по себе уведомление на «Госуслугах» — это ещё не финальное решение. Часто такие сообщения приходят из-за технических сбоев, автоматического переноса данных или когда система просто актуализирует сведения, а реальный юридический факт (снятие с учёта) ещё не прошёл в базе военкомата. Поэтому в разговоре с сотрудниками военкомата важно не спорить, а запросить официальную позицию. 
Что сделать прямо сейчас:
Запросите выписку из реестра воинского учёта. В личном кабинете на «Госуслугах» или на сайте «Реестр повесток» (реестрповесток.рф) можно сформировать выписку — она покажет, действительно ли в системе зафиксирован факт снятия с учёта. Это станет главным аргументом в споре. 
Напишите официальное обращение в военкомат. В письме чётко изложите ситуацию: укажите дату и время получения уведомления, приложите скриншот выписки. Попросите разъяснить, на каком основании система посчитала вас снятым с учёта, и предоставить подтверждающие документы (например, решение комиссии, акт обследования). Ответ желательно получить в письменном виде — это будет доказательством в случае дальнейшего обжалования. 
Воспользуйтесь функцией досудебного обжалования на «Госуслугах». В личном кабинете есть специальный сервис для этого. Подайте обращение, описав обстоятельства, приложите сканы уведомления и выписки. Срок рассмотрения — около 5 рабочих дней, но если потребуется дополнительное обследование, срок могут продлить ещё на 10 дней. 
Почему может возникать противоречие? Система иногда отражает результат уже прошедших процедур (например, медицинское освидетельствование, на котором признали негодность), даже если физически отметка в базе военкомата ещё не появилась. Или произошла задержка синхронизации данных между ведомствами. Поэтому важно не просто констатировать факт уведомления, а выяснить, на каком этапе процесс остановился. 
Если досудебное обжалование не поможет, следующим шагом будет обращение в суд (в порядке Кодекса административного судопроизводства РФ). 
Я советую начать с запроса выписки и официального письма — это сразу снимет большую часть вопросов. Если в ответах военкомат будет настаивать на своей позиции без объяснений, обращение через «Госуслуги» — самый быстрый путь к разрешению конфликта.

Удачи в решении вопроса!