Как выяснилось, при постоянном проживании в Варне надо регистрировать живность в общине.
Стерилизованная собака - бесплатно, нестерилизованная - что-то типа 25 BGN (~500 руб) в год налога.
Сводили собаку к местному ветеринару, который поводил по ее пузу датчиком УЗИ, убедился в отсутствии соответствующих частей и поставил отметку в ветпаспорт. Процедура обошлась в 10BGN.