It should likes the deletion is not getting synced with the server. Does it happen regardless of the computer you delete the items on or does it seem to be a problem with just one computer? If just one, delete the ost file on that computer and let outlook resync.