Having skimmed the EE forums for a while, the only way to create a member search using regular templates is to create a weblog consisting of pseudo member profiles which could be updated by the member via a SAEF. However, while that allows for all kinds of goodies to be included, such as tags, there are obvious issues such limiting the number of profiles a member can submit to no more than 1. At least, this allows for a form which enables a search for a member using multiple criteria.
If a member search was to be included, an option for members not to be included in the search might be nice.