L'EAV est une option valide :elle peut être complexe et gênante avec ce qui devient effectivement des données non typées.
XML avec XPath serait également une option : http://dev.mysql.com/tech-resources/articles/xml-in-mysql5.1-6.0.html
Je pense que la plupart des cas vous obligeraient à générer du SQL dynamique si les champs à rechercher peuvent varier.
