O EAV é uma opção válida - pode ser complexo e estranho com o que efetivamente se torna dados não digitados.

XML com XPath também seria uma opção: http://dev.mysql.com/tech-resources/articles/xml-in-mysql5.1-6.0.html

Eu acho que a maioria dos casos exigiria que você gerasse SQL dinâmico se os campos a serem pesquisados ​​pudessem variar.