I've seen this many times, and I still think that it's the most powerful piece of advertising that I've ever seen.
It combines everything that we take for granted about Google -- the spelling correction, ability to search through multiple datasets intelligently (flight schedules, for example), location-dependent search.
But none of it is presented this way; it's all just seen through the lens of a man navigating life and love. The technology is unseen, and not even mentioned, but the power is very, very real.
http://www.youtube.com/watch?v=nnsSUqgkDwU