Верно: Совет ветеранов совместно с УВД проводит работу...
Выбор предлога зависит от контекста. Ср.: УВД на Московском метрополитене и вы легко ориентируетесь в метрополитене? В большинстве контекстов будет уместен предлог в.
Слово "первый" пишется строчными буквами.
Грамматически верно: УВД по городу Геленджику.
УВД по г. Москве. См. "Письмовник".
Правильно согласование: при начальнике... подполковнике...
УВД, конечно же, неодушевленное существительное, но здесь мы наблюдаем метонимический перенос: организация – люди, работающие в этой организации. Другими словами, под УВД подразумевается "сотрудники УВД".
Правильно: Утерянный паспорт, выданный УВД города Ноябрьска Ямало-Ненецкого автономного округа Тюменской области.
Сочетание указывает на источник сообщения, поэтому правильно его обособление как вводного.