A lot of companies verify postcodes with QAS, so probably worth reporting it to them:

http://www.qas.co.uk/knowledge-centre/product-information/ad...

They are run by Experian who one of the main credit check companies in the UK, so you might be able to hit two birds with one stone :D

Your address should be included in the postcode database if you are registered to vote. Sometimes new addresses take a few months but they should get added eventually.

Go register to vote!