So now that I've upgraded I can fill you in on what you should do to make MT 3.1x work fast. I've covered some aspects in other entries but I'm repeating them here for the sake of completeness.
1. Turn on dynamic templating for at least some templates
This will make your rebuilds quicker, especially if you rebuild the entire blog. MT3.0 did improve areas like posting comments by implementing background tasks but posting entries still can take a while. You should definitely convert category archives to dynamic, and it may pay off to convert all of your archive pages too. Your main index and RSS feeds are probably best left static to reduce server load.
2. Enable caching of dynamic pages
This is explained here. This means that dynamic templates are only regenerated when they have changed and not every time they are requested. This will reduce load on your host's server and on your database especially.
3. Enable Conditional Requests
This is explained on the same page. Basically it means that browsers won't keep requesting your dynamic pages if they haven't been modified - instead, your web server will send a 304 (not modified) HTTP error code and the browser will used a cached copy of the page. This will result in lower bandwidth usage.
4. Don't rebuild your RSD and Stylesheet files with every rebuild
This applies to all recent MT versions, not just 3.1x. Make sure your RSD and stylesheet files have the "Rebuild this template automatically when rebuilding index templates" box deselected. They really need updating and will only slow down your rebuilds. You could make your RSD file dynamic but I wouldn't recommend you do the same for the stylesheet as this is a file that will be requested a lot. Even Wordpress doesn't make its stylesheet dynamic.
5. Remove the cruft from the .htaccess code
The code to go in the .htaccess file has been designed to cope with various environments with and without mod_rewrite. If you know that you have mod_rewrite (all half-decent hosts should provide it) then you can reduce the code down to this:
Options -Indexes
DirectoryIndex index.php index.html index.htm default.htm default.html default.asp /mtview.php
RewriteEngine on
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^(.*)$ /mtview.php [L,QSA]
Not having the conditions in there should reduce the processing time of the statements which may offer a marginal increase in pageload performance.
6. Use Ping-o-matic for pinging
Instead of waiting ages while your blog pings several update monitors when you ping, try just pinging http://rpc.pingomatic.com/. MT by default includes blo.gs and weblogs.com, and the 3.11 release adds technorati.com, which, if they're down or acting slowly, can make posting new entries quite slow. So deselect them all and use that - pinging that once will ping all the main pinging sites for you. Wordpress uses it by default. You can get more information at pingomatic.com.
7. Avoid using lots of complicated plugins
Some plugins will slow down your rebuilds because they require a lot of processing power. A plugin that counts how many words there are in your entire blog, or that has to compute a complex regular expression, will require lots of CPU and more time to process. Avoid them if you can, or include them in a template that isn't rebuilt automatically. Same goes for plugins which contact other servers, especially if the server in question is quite slow.
8. Avoid using lots of conditional tags
By default, the individual archive templates include a number of conditional tags which are used to display different output depending on whether you allow unregistered comments or not. If you have set this and are unlikely to change, you can remove the code block that doesn't apply. The conditional tags will require processing when being rebuilt so removing them should reduce the rebuild time.
9. Use MT-Blacklist
MT-Blacklist 2.x allows you to block duplicate comments which means that files are only regenerated once instead of each time a duplicate comment is posted, and will obviously prevent rebuilds caused by a spam infestation. Also, avoid using lots of regular expressions in MT-Blacklist as this uses up more processing power than splitting up the key phrases into strings and URL patterns.
This is just a start - there are probably many other tweaks you can apply to tune up MT so that it's faster. As a guide, by following these steps this entry took 15 seconds to post - previously it would have taken far longer. But your milage may vary.

Thanks for the tips Neil! These will really help. I haven’t tried out the dynamic pages yet, but I definitely will now.
Nice write-up Neil! These little steps add up to a lot in the end… Thanks for this.
I followed the tips and turning on the dynamic publishing messed up my permalinks, so I switched everything back to static until I can figure this out.
I wonder if Ping-O-Matic could become a checkbox or integrated somehow? You’re much closer to MT development than I am, could this happen?
Thanks for your post. I’m running both 3.11 and the older version (2.5x) at the moment, and I want to convert my old blogs to use the new version but I’m a bit concerned about incoming links. How can I upgrade without loosing the filenames that were there before?