Filtered search with repopulating dropdowns

Hi, I’m looking for a way to create a filtered searchform to search through my posts.
I’d like to make a dropdown that contains all categories (fruit, vegetables, sweets) and a second dropdown containing all tags (banana, apple, beans, spinach, toffee, lollipop).
Then I’d like to do a search on the combination of the choosen category and tag. Sofar, that’s no problem, there’s tons a plugins that can do that.

But if you choose the category fruit in the first dropdown, only the tags banana and apple are going to results in actual searchresults, the combination fruit – spinach won’t contain any posts. (In the structure of my website.)
So I’d like to have some sort of ajax call that repopulates the second dropdown so it only shows the tags that are present in the posts of the choosen category.
So if you haven’t choosen a category in the first dropdown, all tags are availabele in the second dropdown. But if you háve choossen a category, the tags dropdown should be limited to tags that will result in posts in combination with the choosen category.

There are some really nice plugins for filtered search results, with a lot of options, but I haven’t found this feature yet.
I’ve also thought of creating a searchform with gravity forms, but also the ajax repopulation of the second dropdown is too difficult.

Does anyone know a good way to achieve this?
Thanx!