На сколько это правомерно и какие нормативные документы регулирует штрафы по таким делам?

Действия военкомата неправомерны. Назначать штраф без вручения письменного постановления и документов, нарушая процедуру уведомления, незаконно. Требуйте письменные документы и обжалуйте.

Штраф (до 130 тыс. руб.) возможен за неявку по повестке (ст. 21.5–21.6 КоАП РФ), но только после соблюдения процедуры: письменная повестка должна быть вручена под подпись (ст. 4 ФЗ «О воинской обязанности»). Если уведомлений не поступало, оснований для штрафа нет.
Снятие с учёта из-за неподтверждения места жительства — отдельная процедура (ст. 8 ФЗ), но это не автоматически влечёт штраф.
Нарушения со стороны военкомата:

Не предоставляют постановление о штрафе — это прямое нарушение (ст. 29.11 КоАП РФ). Без документа оплачивать ничего не нужно.
Дают только квитанцию — незаконно. Сначала выносят постановление, затем дают платёжные реквизиты.
Ваши действия:

Требуйте письменно:

Копию постановления о штрафе.
Документы, доказывающие, что вам надлежаще вручали повестку.
Если отказывают — пишите жалобу в прокуратуру или суд (ст. 30.1–30.3 КоАП РФ).
Не оплачивайте штраф до получения постановления.
Нормативные документы:

ФЗ «О воинской обязанности и военной службе» (ст. 4, 8, 10) — правила учёта и уведомлений.
Кодекс РФ об административных правонарушениях (ст. 21.5–21.7) — штрафы за неявку по повестке.
Приказ Минобороны № 495 (2023) — порядок вручения повесток через «Госуслуги» или лично.
Итог: Военкомат нарушает процедуру. Требуйте документы, при отказе — жалуйтесь в прокуратуру. Штраф может быть отменён судом, если докажете, что не получали уведомлений.