Мы не понимаем, что они хотели нам этим сказать.

Консульство дало вам правильный ответ в контексте проведенных изменений системы регистрации. Но вы, видимо, снимались с регистрации еще до "реформы" в паспортном столе МВД, а не в органе регистрации местной общины, которому теперь переданы функции ведения реестра. Сейчас при снятии с регистрации действительно выдают справку, подтверждающую, что человек исключен из реестра территориальной общины. Об этой справке или извлечении из реестра и пишет консульство. Но в реестре есть сведения лишь о тех лицах, которые были зарегистрированы в нем на момент его внедрения, о тех лицах, кто выписылся ранее сведений там нет.

Ответ от ЦНАП то же в рамках сегодняшнего законодательства. Они действительно не уполномочены выдавать справки об отсутствии регистрации, если в их реестре нет этой регистрации или снятия с нее. Справку же о том, что лицо не зарегистрировано где-либо, горе-реформаторы не предусмотрели.

Потому я и писал, что идиоты от новой власти, проводя реформы, не учли все возможные нюансы существующих ситуаций.

Буду еще контактировать с консульством, но это какой-то замкнутый круг

Консульство не имеет права требовать от вас вновь зарегистрироваться в Украине, что бы потом сняться с регистрации повторно. Вы уже сняты с регистрации, у вас должно быть лишь подтверждение этому. Справка о лицах, зарегистрированных по вашему прежнему месту жительства дополнительно это подтверждает. Вам стоит обратиться за официальными разъяснениями в МИД Украины и МСУ, изложить свою ситуацию и попросить помощи в урегулировании вашего конкретного случая. Вы живете давно за границей, места для проживания и регистрации в Украине не имеете. Подать обращение можете электронно

https://www.kmu.gov.ua/gromadskosti/zvernennya-gromadyan. Ваш случай далеко не редкий, многие, кто ранее снялся с регистрации, оказались в подобной ситуации. Регистрироваться в Украине в вашем случае быстрее не будет, одна только перспектива общения с военкоматом стоит того, что бы отбросить этот вариант.