As silly as it sounds, this almost sounds like a job for Git. In that case, you could simply revert a single commit, and have the user resolve the conflicts. For that to work well though, you'd need to keep separate "repositories" for phone/Google/Facebook/whatever addresses and merge them locally, which could get very ugly for end users.
