Shoutbox

The easiest way to find a contact at the moment is to go into the Contact List Cleanup where you can sort by either current name or e-mail address.  This is what I use if I'm not sure what someone's current name is but I know what their e-mail address is.  Saves switching to view by e-mail address and back again.

But yes - a search would be useful too.  You might remember part of someone's name but not the first bit.