Have you considered trying to get hold of one of the best sources of address data available outside the post office ? The BBC TV license data. If you could persuade someone to release that as open data without names, bobs your uncle :-)

[addressbot]

http://www.bugherd.com/projects/59635/tasks/12

[giacecco]

Thanks, it's in our Trello for possible data sources at https://trello.com/c/docsY6m8/28-tv-licencing .