So, I thought, how about taking a leaf out of the Hesiod model and just encoding the data into the DNS somehow, e.g.:
senji.livejournal.com IN TXT "Senji|+441632960123|23 Leinster Gardens,London,UK"
With this you could just hand out the domain name for your details and PIM software could update itself as and when needed.
However this runs into the obvious problem that you might not want the entire world to know your phone number, so my subsequent thought is that you hand out a domain name and a key (or multiple keys) to your correspondants and store the actual data encrypted, possibly with more than one record under each name such that the end user tries to decrypt all of them and integrates any that succesfully decrypt.