I have moved nearly every year since I left for college and I hate having to reset every address on every service I have. I'm sick of it.
do pretty much what you're looking for.
My understanding is that addresses in the US are usually derived from the municipal authority and by the time those trickle out to the various consumers (counties, states, feds, USPS, Census, and commercial consumers) it's a mess. There are many initiatives underway to clean this up (usually in the context of E-911 and putting a single point on every discrete unit in a building) but it's a massive task.
Every City has it's own standard (often the whim of whoever has the authority) and there are situations that will make you tear your hair out - the official address being 1000 Some Road but it's a multi family place so the building address is 1020 Some Road, or confusion over whether its 1000 W Some Road or 1000 Some Road W. My personal favourite was the guy who convinced USPS that his address was 1 Unicorn Road (changed for privacy) rather than XXXX Long Avenue. The City ended up making an exception for him. Then there are address like 10 1/2 12 1/2 Avenue.
And don't even get me started on how USPS often use a different City (my understanding is that this dates back to when the US was surveyed and the postal system was established. If your City didn't exist at this time then there is a good chance your USPS address is really the nearest large city).
Geocoding solves the issue if you don't care about spatial accuracy but even that has issues.
123 YOUR STREET
NOT-YOUR-TOWN, STATE ZIP
The mismatch is especially common in areas which used to have dozens of post offices which have now been either shut down or downgraded to PO box-only offices, and all home delivery has been consolidated to a single post office for cost efficiency.
Municipalities assign the rest of the address (street name, house number etc) and are responsible for that mess.
This is for the UK. Dunno about elsewhere. Dunno about competitors in the UK.
I remember having this idea in the late 90s (while in London, moving around frequently) and did a net search and found that there was a provider of such a service even back then. Do not know if it the same crowd since way back then.
Of course all of this automated centralization will result in security holes, so that'll suck, especially if the federal government's fallback is the woefully insecure social security number.