When I delete new messages in my blackberry at night and come back into the office in the morning my messages are still in my Inbox in Outlook. I have noticed the only way I can get my Outlook inbox to reflect what is showing on my handheld is if I do a manual reconcile. Also it is set to handheld wins and our BES server is running version 4.1.0.38
what are your settings in message options - 'delete on'
when you're deleting on the BB, are you deleting multiple messages @ once? (highlighting a bunch or using delete prior) because the desktop won't sync these.