EAV ist eine gültige Option - es kann komplex und umständlich sein, was effektiv zu nicht typisierten Daten wird.
XML mit XPath wäre auch eine Option: http://dev.mysql.com/tech-resources/articles/xml-in-mysql5.1-6.0.html
Ich denke, dass Sie in den meisten Fällen dynamisches SQL generieren müssen, wenn die zu durchsuchenden Felder variieren können.