Кого могут не выпустить за границу

Все возможные варианты запрета на выезд за границу прописаны в статье 15 федерального закона от 15.08.1996 N 114-ФЗ "О порядке выезда из Российской Федерации и въезда в Российскую Федерацию".
Ничего про "не служил в армии" там нет. На границе на то служили вы или нет всем пофиг.
Если лень искать процитирую статью:
Статья 15. Право гражданина Российской Федерации на выезд из Российской Федерации может быть временно ограничено в случаях, если он:

1) при допуске к сведениям особой важности или совершенно секретным сведениям, отнесенным к государственной тайне в соответствии с законом Российской Федерации о государственной тайне, заключил трудовой договор (контракт), предполагающий временное ограничение права на выезд из Российской Федерации, при условии, что срок ограничения не может превышать пять лет со дня последнего ознакомления лица со сведениями особой важности или совершенно секретными сведениями, - до истечения срока ограничения, установленного трудовым договором (контрактом) или в соответствии с настоящим Федеральным законом.
В случае, если имеется заключение Межведомственной комиссии по защите государственной тайны о том, что сведения особой важности или совершенно секретные сведения, в которых гражданин был осведомлен на день подачи заявления о выезде из Российской Федерации, сохраняют соответствующую степень секретности, то указанный в трудовом договоре (контракте) срок ограничения права на выезд из Российской Федерации может быть продлен Межведомственной комиссией, образуемой в порядке, установленном для создания межведомственных координационных и совещательных органов, образуемых федеральными органами исполнительной власти. При этом срок ограничения права на выезд не должен превышать в общей сложности десять лет, включая срок ограничения, установленный трудовым договором (контрактом), со дня последнего ознакомления лица со сведениями особой важности или совершенно секретными сведениями;
2) в соответствии с законодательством Российской Федерации призван на военную службу или направлен на альтернативную гражданскую службу, - до окончания военной службы или альтернативной гражданской службы;
3) в соответствии с уголовно-процессуальным законодательством Российской Федерации является подозреваемым либо привлечен в качестве обвиняемого, - до вынесения решения по делу или вступления в законную силу приговора суда;
4) осужден за совершение преступления, - до отбытия (исполнения) наказания или до освобождения от наказания;
5) уклоняется от исполнения обязательств, наложенных на него судом, - до исполнения обязательств либо до достижения согласия сторонами;
6) сообщил о себе заведомо ложные сведения при оформлении документов для выезда из Российской Федерации, - до решения вопроса в срок не более одного месяца органом, оформляющим такие документы;
7) проходит государственную службу (работает) в органах федеральной службы безопасности, - до окончания срока соответствующего контракта (трудового договора);
8) признан несостоятельным (банкротом), - до вынесения арбитражным судом определения о завершении или прекращении производства по делу о несостоятельности (банкротстве), в том числе в результате утверждения арбитражным судом мирового соглашения.

Могут ли не выпустить в страны ЕС, если человек не служил в армии, уже не учится в университете, но возраст еще призывной? Этот пункт точно не волнует их. Исключение, если Вы в списке уклонистов.
Сообщение о себе заведомо ложных сведений при оформлении документов для выезда из РФ
Непогашенная судимость
Недействительный паспорт или просроченный (в том числе и российский)

идиотов точно не пускают