Unfortunately for a board your size, the internal option really isn't an option. It has to do a "like" comparison on every post.
Since you're running on a dedicated server you're probably better off modifying the minimum character limit for mysql's fulltext engine. The indexes will have to be rebuilt, so you'd be looking at a bit of downtime to do it however.
http://dev.mysql.com/doc/refman/5.1/en/fulltext-fine-tuning.html
