A couple of ideas....
Do you know anything about where they attended school? And by this I mean everything from grade school to grad school....you could look around on classmates.com, see if there's any kind of alumni group.
Do you know any names of this person's family - parents, grandparents, siblings, etc. Check for the family-names. Also check for any family-connections on Genealogy.com.
Google their name. Google any known associations you have for them - family, business, education, places of worship, etc. Contact any sources that seem good - someone might have their present address.
Do a search for their name/family/business at the local newspaper's archives. If any family-membsr got married while they lived there you might even find details - relatives' names, church-name, etc. Same holds true for funerals.
Facebook is good - do a search for their name and for any other known associations. (Maybe even try twitter or any of the other social-networking sites.)
Do you know what this person did for a living? Were they licensed in any way?
If you know their old address, send a letter to that address with their name. They *might* have a forwarding address on file with the Post Office *or* sometimes the people at their old house will write the forwarding address on the envelope.
Did you know any of their hobbies? Were they members of any community sports-teams or the local theatre? Could you call these groups up and tell them you're trying to get in touch with your Mr./Miss X?
I know you mentioned the whitepages but have you tried whitepages.com? Do a reverse lookup for their name in the town/state they lived in. You might get a hit. If their name is at all unusual you can even do a nationwide search for their name and see how many hits you get.
Good luck,
agnes!