I noticed that on exchange 2007 sp1 I had a  limit on mailboxes, even though the DB limits were set to none and individually the mailbox limits were all un-ticked.

outlook and owa both complained, although OWA was nice enough to let me know the exact nature of the problem "your mailbox has exceeded.....|, Outlook was a bit more cryptic.

I'm going to see if this is a known bug and post back.