[]"Did switching off full tracking make the response time acceptible?"
Yes, it made a rather large difference. It is annoying to check the board without it though

[/]
I've also heard that upgrading to MySQL 4 can help, but don't have personal experience with this.
Is your MySQL configuration file tuned optimally for your server? The MySQL distribution includes three or four sample config files, designed for different situations. Then you can customize it further yourself.
I don't know enough about MySQL to help with this, but others might be able to help. Also, I think that at mysql.com, you can pay them for a custom tuning.