История дальше: Мы не пошли оспаривать отказ, а решили подать заново.
При этом сразу же позвонили в территориальную ИФНС (в которой заранее объяснили всю ситуацию в "адресном" отделе и сдали гарантийку от собственника со всевозможными контактами). Ежедневно звонили и интересовались: пришел ли им запрос из 46ой... Запроса из 46ой так и не дождались. А в день получения документов, получили отказ, с пометкой того, что 46ая отправляла запрос в территорию, от которой получила ответное письмо с запретом на регистрацию по данному адресу.
В результате, компанию зарегистрировали, но по другому адресу (заказчик в последний момент передумал, и сказал: не зря не проходило). )))