This can be handled by 301 redirect or it can be built into the protocol. When moving a profile from one provider to another, the standard could require a response indicating the location of the profile for a minimum period of time (such as a week or a month).
A standard such as this would be crawled on a frequent basis by the social network apps built on top of it, as well as the search engines. They would all update their canonical profile addresses and that would be that--an organic, self repairing network.
That works if you have a domain name just for your "identity", but if you are hosting on someone else's then it gets interesting.
Of course I may be stuck on the way I was looking at it of a fully qualified URL (say http://runevault.com/runevault for my id, and I don't think DNS currently goes farther then domains).
I think DNS is the key here; it lets you move a server while keeping the same name.