Multiple search – need advise

I’m building a business directory website in which the search function is one of the most important pieces. What I want to make is that people can search categories in a dropdown (school, church, library) and optional there are several multiple search boxes like keyword, city, name of business, telefphone number and a dropdown for state and country. So the search could be – A school in Amsterdam with keyword school and name of school must include ‘school’ (hope you understand).

Is there a plugin who could do this? I need some advice how to make this.. should I use taxonomy for the city, keywords or should I use tags.

Looking forward for your advice, hints & tips ??