In dimp/Dynamic the mailbox would fail to load and the message "Error communicating with Server" would be displayed, this was triggered by ajax_error (that's about as far as we got debugging).
In imp the mailbox would show thousands of messages but they would mostly say "Invalid Address" and "Unknown Date" with "No Subject".
Looking around we finally found this bug that shows it's due to bugginess in the UW-Imap server (time for dovecot).
The fix was the following line in imp/config/backends.local.php:
'capability_ignore' => array('ESEARCH')
After that we restarted apache and all was well.