I use plaxo.com because it is free and will merge your contacts from Outlook, Gmail, and others automatically. I use the notes section to record when I last contacted the person, some stuff about their interests, etc.

The problem with this method is there is no built in way to remind me to make contact with someone who I have lost touch with. Also, the notes section is not searchable-- kind of annoying.

I recently heard of contactually.com that provides a notification system for reaching out to old contacts. I have not tried it yet.