As noted in this posting, we migrated to Maildir. It went relatively smooth, and faster then anticipated. I'll be posting the code to the actual migration script (41 lines of PHP code), and the code code to the milter that temporary locks the mailbox (aboyt 150 lines of C actually written by me). This way, it reduced downtime to the actual time needed to do the conversion, instead of shutting down the whole MTA.
The source for the PHP script and milter are here.