Google now has search in pinyin. That means that you can search for a word in romanized form, and at the top of the results Google will suggest the characters you probably meant to search for. It's explained better in the Chinese FAQ.

Tower Records's Japan site has had something like this for a while: search for the last name of Pizzicato Five front-man Konishi (Yasuharu), and it will present you with a list that includes 小西康陽, his name in Japanese (along with a few other choices, including superstar sumo wrestler Konishiki; don't laugh yet, come over to my place and you can watch the episode of Hey Hey Hey Music Champ where he sings My Hula Wahine while strumming an ukelele).

Another cool Google feature found in the Chinese FAQ is simplified-traditional switching. For example, if a person searches for “计算机”, a common word for "computer" on the mainland, it will also return results for “电脑”, a term for "computer" that may be more used in Taiwan or Hong Kong. Not only that, but when it returns the search results it will convert the title and page abstract of each result on the search results page into the character set that the original search was performed in. Pretty neat!