I am getting 5 or 6 of these errors a day Emailed to me from the System:

Error that occurred: C067-Database store number is invalid
Type of message: OPENED status
Date/Time: Thursday, 27 October 2011 8:40am
To requeue, save the last attachment to <post office path>\WPCSOUT\OFS\0

Background: This Post office had some issues with the Windows 2008 OS, so about 300 users were Moved to another post office.
I deleted the Post office, removed the server and two days later created a brand new server using the OLD name, created a New Post office with the old name.
Created a New test user on the server with no issues for more than a week. Just added two new users and then this message is appearing.
If I resubmit the message it returns with the same message.
I Resynced the Domains, Post offices, and Groups, and Gateways
I ran the Post Office Analyze/Fix Databases with Structure, Index check, Contents, and Fix the results did not show any errors.