Мы жили в трех разных городах и переезжали 5 раз и никогда у нас не было с этим проблем.  Почему вас зарегистрировали через два месяца? Первый счет пришел через два месяца? Контракт об аренде дома/квартиры у вас к тому моменту был? Почему вы не захотели временную регистрацию? Чем отличается сервис временной регистрации от обычной?