As the developer of a similar iPhone app which was GMail only (EmptyInbox), let me just say: IMAP is really, really hard to get right. Each different mail provider is different and nobody is keeping all the rules. Even Google had a few hacky differences to the "official" IMAP way of doing things.

I can completely understand why Mailbox only supports GMail and iCloud...so actually, we need to be getting on Google and Apple's case rather than app developers. Not that I'm biased or anything...