Hi Barry,
Sounds like the syncs did not work with the server, I would normally suggest
clearing the cache first like you noted below. The Rebuild likely does this
as well, since he was able to delete most of the messages.
One thing to try, force sync the deleted items folder in Entourage, since it
is really a move message that may update Outlook. Also doing an empty trash
and forcing sync would be good to try as well as empting the cache on the
deleted items.
In outlook, there is a folder called Sync Issues in the root of the mailbox,
may want to check and see if any of the messages are noted there. Seems
more like an Entourage issue based on the description.
One other place to check is to connect with OWA and see if it is the same as
Entourage or Outlook. Can also delete them from there or Outlook to see if
they go away or not. (Do they come back if you delete them from Outlook?)
Otherwise, it sounds like the remaining ones are still there and not
accessible, just an obvious guess. You could try finding them using
spotlight if that is enabled, just in case in a folder you can't see but if
it shows up you might be able to open it up.
I have not heard of an issue like this before, others I talked to have not
either. The last resort would be do create a new identity to use, but will
require a full re-sync from the server which may or may not be bad for the
user depending on how much mail they have stored up there.