EAV е валиден вариант – може да бъде сложен и неудобен с това, което ефективно се превръща в нетипизирани данни.
XML с XPath също би бил опция: http://dev.mysql.com/tech-resources/articles/xml-in-mysql5.1-6.0.html
Мисля, че повечето случаи ще изискват от вас да генерирате динамичен SQL, ако полетата за търсене могат да варират.