Best way to add a search function to user profiles
You could code up a form_alter() in a custom module that could put search in that admin page.  Or, you could just use www.yourhost.com/search/user to search user accounts.  And if you have advanced search and are using content profiles, you could also restrict your regular node search to that content type, eg type:profile terms to search for in those nodes.