Отказ в выплате надбавки за выслугу лет военному

Нет, к службе в органах внутренних дел! Так и в трудовой книжке записано "проходил службу в органах внутренних дел".

Тогда не понятно, почему вам отказывают, учитывая следующую норму постановления Правительства РФ № 1074:

2. Военнослужащим в выслугу лет для назначения надбавки (далее — выслуга лет) засчитываются в календарном исчислении следующие периоды:
л) служба в органах внутренних дел, милиции (полиции), исправительно-трудовых учреждениях, военизированной пожарной охране, других учреждениях и формированиях органов внутренних дел (охраны общественного порядка) Российской Федерации и Союза ССР в качестве лиц рядового и начальствующего состава;