I'm a little bit OCD about two particular functions of my digital existence: my contacts/address book and my music library. Both have to be tidy, maintained and up to date. For my contacts in particular this means that occasionally I pester people for their current details and even prune out acquaintances that I have had no contact with in a long while. I have a few observations and habits to share, there's no revelation here only insight into my approach for what it's worth. I find that a good indication of how well I know someone is the completeness of the information I have for them. By the time I have someone's physical address I have a significant relationship with them, be it friendship or something more professional. I also like to have contact photos for everyone wherever possible. I'm terrible at names and if I don't know someone very well then having their face show up on calls or when I'm browsing for them is very helpful.
I also know a lot of pretty people!
Social media is a good way of maintaining someone's contact entry without having to harrass them. People will tend to keep their Facebook, LinkedIn or whatever details current and relevant and checking their page when you suspect something has changed is a less intrusive way of making sure you're not spamming an old unused email account or texting an old phone number. Some social websites will integrate with your mobile device via apps which can assist with this.
It's also a good idea to be selective about which of your own information you share. OS X Lion handily lets you choose which information is shared on your vcard, but where this isn't an option maintaining a second 'sharable' entry for yourself can be useful.