I have used Gmail for many years, and during this time I have deleted a lot of email messages and contacts.
I discovered that when I use some services (for example, DropBox) to invite my friends by my Gmail account, Google also suggests to me contacts I deleted a long time ago!
Why? Where is Dropbox finding these old contacts?
Best Answer
In the future, you can take off auto-additions for contacts as explained in the Google support page Creating contacts.
For the contacts you already have, feel free to clean those Google contacts up by clicking on the Mail button in the top right of Gmail and go to contacts (Do check out both MyContacts and OtherContacts within your groups).
Lastly, if you're interested in making sure you have all the contact information for your contacts, you might consider trying out the solution my company has come up with to automatically update your Gmail address book: http://writethat.name/