Hi Garfield,
Have you tried checking your exchange database for any inconsitencies? Isinteg and edbutil. Also, you could try exporting the information from the mailboxes, then deleting the mailbox, recreating them, and then re-importing the mailbox contents back to it.
LGI, are you sure there was no error code ec=***?
hope this helps,
g