How do I setup a searchable database in excel

I am trying to setup a searchable database using excel. The data is pretty
massive (e.g. 250 columns and 300 rows). I have seen this done before. The
idea is to have an interface with either a drop-down menu or checklists to
call all of the data that match the desired criteria.

The best illustration that I can think of is an interface like the advanced
interface of ebay (but without the free text box). You can check-off a
variety of criteria and then it calls all of the data that match that
criteria.

I have played with the auto-filter button, but even with custom filters,
this does not allow me to select enough criteria. I think that Advanced
filters may be a possible solution, but I am finding it complicated to use.

VBA may be the best alternative.

Please think about this and respond with any suggestions. A
template/model/document that is similar would be much appreciated.

Thanks for all of the help,

Jon