Hola Gothgauss:
Complementando el comentario de quimfv, dependiendo del tipo de tablas que estés utilizando podrías considerar utilizar búsquedas de texto completo:
http://dev.mysql.com/doc/refman/5.0/...xt-search.html
Este tipo de búsquedas es mucho más flexible que utilizar LIKE, aunque pueden usarse sólo con tablas MyISAM. De cualquier manera te recomiendo que le des un vistazo a la liga que te puse.
Otra opción, aunque bastante costosa en cuanto a rendimiento, es que separes tu cadena y busques cada palabra de manera individual, es decir algo como esto:
Esto te permitiría obtener resultados independientemente de la posición de las palabras, es decir podrías poner
"frito tomate" o
"tomate frito" y ambas regresarían resultados.
Saludos
Leo.