Open Store that is used by this note was not found

I believe this error is happening because I have shared mail on my old server. Here is what has happening. I have requested all my user mail box to move to a new 6.5 server. The old server was 4 and graduated to 6.5. I request the move to the new server and all seems well. A few of my users, who I created on the old server with the 6.5 version, moved over to the new server and lost their template design. Half the template look like 4.6 the other half is 6.5. I tried to update the template but this does not work. I tried using a blank template then updating to the mail template. No go. So, I contact Lotus and they gave me reference number 1110903 Copy Mail box. This worked for one user. The others that I have encountered get the “Open Store that is used by this notes was not found” for shared mail documents. My only recourse is to restore their old database to the server and hope for the best. This restore brings the mail box back to it original state before the move. Then I have to copy any new mail to the restore and manually move the mail box to the new server. Problem is now my migration of mail boxes are getting old and I am not successful in bring over all the documents.

Does anyone have a solution to fix the mail box on the new server? Or any documentation on this problem that may be helpful?