I opened a support case and even had a web-meeting session with the support tech. I was able to show him the problem actually happen and they took log information. I haven't heard back from support, but the sales person says the issue was closed because they could not replicate it.
I suspect the issue is caused because 2 of the PCs were upgraded from XP Home to XP Pro and originally had Office 2000 - which was uninstalled and office 2003 was installed. This may be the reason, but it's no excuse.
Unfortunately, my client has nearly missed several court dates (lawyers) so this issue has become unacceptable. They have switched to google calendar for now and are looking for a different solution.
I realize that this issue may be user error (perhaps they aren't syncing enough - though in our testing they sync'd each time) but the users are using outlook as they'd expect it to work. Deleting events is just unacceptable.