I managed to clean up some redundant data with SQL:
First, from fo_searchable_objects:
DELETE so.*
FROM fo_searchable_objects so, fo_mail_contents mc
WHERE so.rel_object_manager = "MailContents"
AND so.rel_object_id = mc.id
AND mc.is_deleted = 1
Then, from both fo_mail_datas and fo_mail_contents:
DELETE md.*, mc.*
FROM fo_mail_datas md, fo_mail_contents mc
WHERE md.id = mc.id
AND mc.is_deleted = 1
...and then optimized the tables and reduced the size significantly.
I'm not yet sure if I broke anything, but there don't appear to be any ill effects.