I'm getting the error ...
Task 'Receiving' reported error
(0x8004210C) : 'Some messages you marked for download are
no longer available on the server.'

This seems like this will be a common situation for those
of us that travel and will be deleting messages from
either machine.

I had a similar problem as well in the inbox for 2003. I couldn't delete
the header because it says I have to download it from the server but the
server didn't have it anymore!

I then went to Tools/send and receive/process all marked headers and the
headers finally disappeared from my Inbox.