[kmike]

Basically, once you hit the magic number of 3 million posts, the MySQL fulltext search times start to increase exponentially. And it'll only get worse with every new post added. I guess every board has to go through this once it reaches 3-4 million posts.

No amount of server tweaking is going to help here. Converting to InnoDB won't help as InnoDB doesn't have a fulltext search capability. Your only choice is a slave search server, preferably dedicated, though you can try the approach from the first post, it may work if you have a sufficient hardware in your db server. I'll be interesting to know if it worked for you.