Форматирование (нормализация) почтового адреса для поиска дублей?

дешевая рабочая сила вас спасет :)
а вообще можете нормализовать адреса через dadata.ru, а потом попробовать помэтчить
только с домами строениями и квартирами придется повозиться

Можно сделать при изначальном отсутствии какой-либо нормализации совсем странный способ — найти апи карт и сравнивать возвращаемые координаты по хешу например.

Попробуйте использовать API Яндекс.Карт, сравнивая выдачу геокодера. Документация.

Ну вас спасет дешевая детская рабочая сила.
Нанимаете фрилансеров по доллару в час и пусть перебирают.

У меня когда-то давно (лет 12-13 назад) стояла похожая задача. Я приводил к нормализованному виду в несколько проходов
1) Перевел все в один регистр (верхний)
2) Заменил все «пр.», «просп.» и «проспект» на что-то одно. ТО же самое проделал с квартирами, домами, строениями и прочим.
3) На основании всего этого уже сделал 3 норм. форму.
4) Разобрался с адресами, которые не смогли нормализоваться
НА базу с 25000-30000 адресов я потратил 2 или 3 дня.
Понятно, что решение в лоб и может быть не совсем эффективное, но альтернативой было ручное перезабивание всей этой информации, что несколько не устраивало меня :)

Система Papyrus (www.petroglif.ru) умеет это делать. Но ваша проблема — заказная: импорт-парсинг-экспорт. За небольшие деньги можно легко осуществить.