I'd have to admit that I like the "just type and searchbox appear" solution... it fits the desktop-contact-search idea of the OS...

But a directly visible searchbox is better then the menubar solution...