gregbo - 8:32 pm on May 19, 2006 (gmt 0)

Hmmm ... As AskJeeves, Ask relied heavily on branding -- certainly, the butler and the "type a question" feature were key to the brand image.

While not (totally) a search engine, one could argue Y!'s "life engine" campaign was an example of (re)branding.