We have two themes which could essentially fit the bill.
Vantage is our business directory theme, and
ClassiPress is our classifieds theme (however, this could be modified to suit). The reason why I mention both is that whilst Vantage is probably the best fit for the project you describe overall, what it doesn't currently have that ClassiPress has, is an advanced search functionality which will allow your users to search by custom fields which you determine (hence, allowing searching of the fields you describe - you can see this functionality on the
ClassiPress demo site in the category view sidebar as "refine results"). In saying this, you could still modify Vantage to offer this functionality also.
AppThemes does not offer customization services, however we do have a
certified partners page where you can find developers for hire. If you make contact directly with an outline of your requirements, they can provide a quote for the work. Thanks.