Links for reference to accomplish the URL rewrites needed to preserve old search-engine links and to combat general bit rot:
WP official info on MT imports (old but with a lot on redirects)
Mudita on the migration and redirects (2005 updated in 2010)
Basically, there are three components: using .htaccess, ensuring that the WP import has access to the old MT post numbers (something I don’t think I spent time on at import), and determining the best way to combine this data. One possibility is actually to do a cold .htaccess mapping on a post-by-post basis but that would involve forcing 404s to run through a text search of about 7000 lines which sounds like a bad idea.