Отказ в получении звания "ветеран труда", правомерен?

Вам отказали неправомерно.

согласно пункту 4 статьи 7 фз "о ветеранах" порядок и условия присвоения звания "ветеран труда" определяются законами и иными нормативными правовыми актами субъектов российской федерации.

в соответствии с пунктом 2.1 положения о порядке и условиях присвоения звания "ветеран труда" и выдаче удостоверения ветерана труда в городе москве, утвержденного постановлением правительства москвы от 27 июня 2006 года n 443-пп
звание "ветеран труда" присваивается гражданам,
награжденным орденами или медалями ссср или российской федерации, либо удостоенным почетных званий ссср или российской федерации, либо награжденным почетными грамотами президента российской федерации или удостоенным благодарности президента российской федерации, либо награжденным ведомственными знаками отличия за заслуги в труде (службе) и продолжительную работу (службу) не менее 15 лет в соответствующей сфере деятельности (отрасли экономики) и имеющим трудовой (страховой) стаж, учитываемый для назначения пенсии, не менее 25 лет для мужчин и 20 лет для женщин_или_выслугу_лет, необходимую_для_назначения_пенсии за выслугу лет в календарном исчислении.
в выслугу лет, необходимую для назначения пенсии по линии мвд, срочная служба в армии входит (пункт 1 постановления совета министров - правительства рф от 22 сентября 1993 г. n 941).

вам следует взять в отделе кадров справку с подтверждением выслуги лет и еще раз обратиться в соцзащиту с заявлением, со ссылкой на указанный пункт постановления правительства москвы.