Sometimes MySQL just isn't quick enough. Especially when it comes to fulltext searches. Everything needs to be indexed correctly, and if we're using different fields with different weights for a relevance percentage, things get very complicated quickly. Xapian to the rescue.
The Xapian library can be compiled and installed as a binding for your PHP installation. He includes some sample scripts to get you started - the SQL to build the table, a Xapian wrapper class, and three simple PHP scripts to search for, view and delete records. Some sample results are also included.