Похоже, что с помощью решения регулярных выражений (приведенного выше) вы получите достаточное количество адресов. Вы упомянули, что готовы принять довольно высокий уровень погрешности, но это не обязательно. В зависимости от того, насколько чистыми вы можете получить данные, вы можете выполнить некоторую очистку списка адресов или «очистку», как это иногда называется. Это когда вы берете неверно сформированный адрес (в зависимости от того, насколько плохо он был извлечен из HTML) и запускаете его через механизм стандартизации, а затем через механизм проверки. Много раз, это будет принимать недоставленный адрес и возвращать полностью квалифицированный и доставляемый адрес. Я говорю об адресах USPS (США), потому что с этим у меня есть опыт, но я уверен, что есть и другие страны, которые имеют подобные услуги. Эти услуги могут выполняться в режиме реального времени или в пакетном режиме, в зависимости от ваших потребностей. Большинство из них также относительно быстрые. Надеюсь, это поможет.
Я работаю в компании по проверке адресов, которая называется smartystreets.