Version 4.0.1+ has full-text search capabilities that you allude to.
mysql> SELECT * FROM atable WHERE MATCH (field1,field2)
-> AGAINST ('+term1 +term2 -term3' IN BOOLEAN MODE);
This capability is only provided for the MyISAM table type.
There are no versions of MySQL, AFAIK, that...