Okay, maybe I'm late to the party, but I saw an article in the WSJ today about a new Google service. You dial 1 800 GOOG411 and you can do a directory-information search for free via Google. Around here a regular directory-information call is about $2.
Google uses voice-recognition to understand what city and state you want and then the subject. It replies in a synthesized voice a few seconds later with the top 5 hits, and even offers to dial a number for you.
Cool. I just cannot imagine the size of the server farms that these guys must have at this point.
EDIT:
I should have mentioned that this is for USA telephone listings. I don't know if it works for international numbers, but I doubt they have spread to that degree.