Pessoal, já que ninguém respondeu, vou contar a experiência que tive até agora a título de contribuição:
Segundo a atendente da Secretaria Municipal de Fazenda de Niterói (prédio da "Prefeitura Velha", Rua da Conceição nº 100), no balcão, empresas cujo endereço é somente "Ponto de Referência", em endereços residenciais, não é necessário busca prévia, que eles chamam de "Consulta de Viabilidade".
Para os casos de lojas, obras, etc é necessário dirigir-se ao prédio da Prefeitura Nova (próximo ao colégio Liceu Nilo Peçanha), 12º andar e solicitar uma Consulta de Viabilidade, tendo em mãos a escritura do imóvel, identidade do proprietário e nº de cadastro do imóvel (IPTU). A Consulta fica pronta em 7 dias.