Is this happening to all users? You mention both OL2003 and 2007.
Is everything up to date - server and clients on all latest SPs. updates,
etc?
Does an item added in Outlook make it to OWA?
How about a contact or task in OWA ...does it show up in Outlook?
OK - but is this happening to *all* users?