The error event 623 gets generated immediately at the start of the Information Store service. So far we've only witnessed this on some Exchange 2003 Servers. Please note that this is specifically about this event being generated after the IS start. There were other causes of even 623 that we had fixes for already.
When this behavior occurs, you may see the Information Store appear to take upwards of 45 minutes to fully respond at service startup. Monitoring "Version Buckets Allocated" (viewable with Show Advanced Counters - see Nageshs' excellent post here: http://msexchangeteam.com/archive/2006/04/19/425722.aspx) will show the Store is immediately running high (over 70%) and until the number falls the Information Store will be unresponsive to clients and ESM. After Version Buckets Allocated falls, the server responds fine and no other issues are observed. 623 errors go away. Restarting a 3rd party server that ties into users' mailboxes (if present) or restarting the Information Store service may cause the issue to occur again.
This problem occurs because of a large amount of hidden search folders that have been created by applications (other than Microsoft Exchange) that have access to users' mailboxes. When the Information Store starts, it becomes available to the host of 3rd party applications which might reconnect and want to sync the contents of the search folders at the same time. These search folder updates can then result in the search folders for a user's mailbox to all be updated at the same time. When a mailbox has a large item count in the Inbox folder (more than 5,000 items) you can experience higher than normal store CPU % utilization and Version Buckets Allocated spikes which can lead to version store out of memory problems. Depending on the type of search performed, the impact can be greater or smaller. Once version store cache has been depleted, the offending transaction gets canceled or it times out and is rolled back and everything moves along as if nothing happened. That's why the event 623 eventually corrects itself.