Табличка из локальной базы, попадаются адреса в разных форматах.
Форма заполнения этой таблички не должна позволять отклоняться от существующих адресов(более-менее), как минимум населенный пункт/район/улица должны выбираться из готовых списков, а не вводиться в ручную.
А дальше при обновлении данных в базе и если адрес пользователя попал в список отключенных - шлём ему оповещение.
Это если у вас пользователь как то имеется в системе с контактами, иначе через Почту России долго будет имхо.
подводные камни - данные могут в течение дня несколько раз поменяться,
ничегоне мешает при исключении адреса из бд высылать ему "ой, ошибочка вышла"
а второе - поиск по адресной базе сомневаюсь что выйдет быстрым.
В итоговой базе у вас будет 3-4 числовых значения - код города, код района, код улицы. Номер дома и квартиры может быть в текстовом формате, но это короткое хорошо индексируемое поле. Все должно работать достаточно быстро, тем более что оповещений будет сильно меньше реальных пользователей.
