I have now combined the above hack with jasons memberlist hack. It is possible to create your own extra fields, and to have them shown, and ones you don't want not shown, in the users memberlist.
my user memberlist shows just the user name, registered on, and my 2 extra fields, bike and other clubs.
(http://www.langportrd.f2s.com/images/memberlist.jpg)
although not a true search function, this could meet your needs. your members would put the details you want in the profile, other logged on members can quickly scroll through the memberlist for the particular detail they want, then click on the link to the full profile and that users pics.
You can also add the 'sort by' function to this page, so if you users wanted to look by hair colour, they could sort by that, and all blondes would be together.