After fustrating for a couple of day without a solution, I've decided the call the MS tech support guys. They found event error 9667 in the Exchange 2003 server. It's not even related to the OAB.
Failed to create a new named property for database "First Storage Group\Mailbox Store (EXCH2003)" because the number of named properties reached the quota limit (8192).
http://support.microsoft.com/kb/820379/en-us fixed it.
Thank you all for the effort.