As I'm aware Magento advanced search does not offer a category search and therefore followed this tutorial to add it in http://www.magentocommerce.com/wiki/5_-_modules_and_development/search_and_advanced_search/how_to_add_search_by_category_to_advanced_search

However this only brings up the top level categories and I need to search by multiple sub categories with an AND clause. How can this be achieved?

Adding more category dropdowns manually just outputs this query string without filtering properly: /catalogsearch/advanced/result/?category=15&category=20