I’ve looked at what others are doing, and for the most part, they all only have one category search though they do provide additional filters in addition to the category search. This is one area that I can improve and will be. I have a new store locator type of extension in the works now. The basic search includes category, radius and keyword which are all fairly standard offered by other products.
The issue with offering multiple category drop down search comes right down to how to provide that feature in a flexible package that is easy to configure so it can meet everyones differing expectations. I just don’t see that as a basic feature, so we’ll disagree :)