Initial Outlook cache sync causing serious performance issues and locking users out of mailboxes

I'm running Exchange 2003 SP2 and have two Outlook 2010 clients connected to the database.  One of the clients is using cache mode and working just fine.  The mailbox size on the server is 25 GB's.  The other user has a mailbox size of 28 GB's.  The first user was able to sync (cache mode) their entire mailbox with no problem.  (6 hours later) When trying to set the other user to cache mode it gets about 30% and hangs.  I then get the below events in the server event logs.  The mailbox never starts the cache (folders generate but that's it) and then eventually both users get locked out of their mailboxes temporarily.  Below are the events I'm getting in the event log.  I've installed hot fix 919417.  It didn't make a difference for once I try to set the user's mailbox to cache mode the same symptoms and errors occur.  Once I quit the cache request eventually the mailboxes respond again.  One difference between this users mailbox and the other is there are less sub folders.  Other than that the mailboxes are about the same size.

Any suggestions?

Event Type:      Warning
Event Source:      MSExchangeIS Mailbox Store
Event Category:      Background Cleanup
Event ID:      9791
Date:            11/22/2010
Time:            11:24:46 PM
User:            N/A
Computer:      BACKEND2
Description:
Cleanup of the DeliveredTo table for database 'First Storage Group\Mailbox Store (BACKEND2)' was pre-empted because the database engine's version store was growing too large. 0 entries were purged.

For more information, click http://www.microsoft.com/contentredirect.asp.


Event Type:      Error
Event Source:      ESE
Event Category:      Transaction Manager
Event ID:      623
Date:            11/22/2010
Time:            11:19:43 PM
User:            N/A
Computer:      BACKEND2
Description:
Information Store (2420) First Storage Group: The version store for this instance (0) has reached its maximum size of 85Mb. It is likely that a long-running transaction is preventing cleanup of the version store and causing it to build up in size. Updates will be rejected until the long-running transaction has been completely committed or rolled back.
Possible long-running transaction:
      SessionId: 0xBD531420
      Session-context: 0x00000000
      Session-context ThreadId: 0x00001360
      Cleanup: 1

Event Type:      Error
Event Source:      MSExchangeIS Mailbox Store
Event Category:      Logons
Event ID:      1022
Date:            11/22/2010
Time:            7:50:38 PM
User:            N/A
Computer:      BACKEND2
Description:
Logon Failure on database "First Storage Group\Mailbox Store (BACKEND2)" - Windows 2000 account DOMAIN\user; mailbox /o=First Organization/ou=First Administrative Group/cn=Recipients/cn=alias.
Error: -1069

For more information, click http://www.microsoft.com/contentredirect.asp.