Integrating this type of feature might do it well:
http://www.daemonprojects.com/phpsnip/view.php?snip=7
Currently all the search terms have to be in order, so this would break the search terms apart and find the search terms even if they are not all together. Would be a start, anyway. Any other ideas?
Some other links:
http://www.phpbuilder.com/columns/clay19990421.php3
http://www.mysql.com/doc/en/Fulltext_Search.html
http://search.mnogo.ru/
http://swish-e.org/