And it doesn't seem to be as tough as I first thought:
Since Thunderbird Mail directories ($HOME/.thunderbird/*default/Mail/) seem to be a series of mbox formatted files, I've found a script to convert from the mbox to the maildir format. It's a perl script called mb2md.pl
It took 6-7 minutes to digest and convert 96 mboxes and thousands of messages for my own mailbox. I'll try it on the other mailboxes and report back once I'm setup with imap.