Gmail has a new Labs experiment: search auto-completion. I was a bit disappointed with this feature, as it didn't auto-complete certain words I tried and knew were there, but that it was mostly focused on auto-completing names/ email addresses.

http://gmailblog.blogspot.com/2009/04/new-in-labs-gmail-search-made-easier.html