Podrías probar (si usas Mysql 4.0.x en adelante) las busquedas "Full text" pero en modo "Boolean":
http://www.mysql-hispano.org/page.php?id=15&pag=4
En principio con ese tipo de busquedas hasta puedes usar ciertos operadores: + - .. etc para definir mejor que busqueda quieres hacer.
Un saludo,