How to: CustomPress & Custom Search functionality

We have client that wants to use CustomPress for a searchable image database project. The default WP search not very good, and is not adequate for this project. They want a robust search that will be able to search multiply custom post tags, categories, etc.

They want a search something like lexisnexis "combined search"

What robust search plugins do you recommend that work with CustomPress?

I understand that some of this will have to be custom coded.