I created another plugin few days back, it’s called Advanced Search Widget. I’ve created many customized search form for many clients, they were same kind of tasks. Searching through taxonomies and custom fields.
So I built this plugin, you can build your search form as you want with custom fields and taxonomies. Drag-n-drop, well, not pure drag and drop form builder, but similar. You can define your search field type and comparison type and can build the search form on the fly.
This is a premium plugin this time, see the details with screenshot.