These services all vary in terms of how they gather their information and what kinds of information they will give you. For example, Internet Address Finder and WhoWhere? turned up some email addresses that have not been valid email address for me for over five years! Most likely these service picked up my email addresses from old Usenet and mailing list postings. Also, it appeared that my initial entry in bigfoot came from an old WHOIS record from my domain registration at the InterNIC. Obviously, not everyone has a registered domain with the InterNIC, but that's another perfectly valid source of information.
All of the services I've mentioned will give out much better information if you register with them, which is a pretty easy process. Most of these services will give you a "permanent" email address as well. Registering yourself is as easy as filling out a simple form and giving as much or as little information about you as you want the Internet to know. About all I give out typically are my emails, web pages, and some places I have been in the past like college and high school. I think this is typically enough for people to find me on the Internet. I'd rather not have strangers knowing things like my address, telephone numbers, and my interests, which are things you can enter into these registration services.
Most of these services will let you enter and search basic information for free. For more advanced features of the service, including email service, the services may charge an extra fee. If you're hoping that some lost friends find you or you want to find some lost friends, check these services out.