I would build, with lots of security help, a single store for peoples information. You could set your address, back details, phone number, etc. You would then grant permission for companies to access subsets of your information. So when you move, you change your info once, and all companies would automatically get updated with your new info.
While this is totally possible now, the security goes a little over my head, and getting everyone else to integrate would be a huge mission.