The old version was Outlook 2010 Beta, and we've encountered it long time ago, than it magically disappeared. After uninstalling the beta version and installing the retail version, the problem arose once again (same OST as the Beta handled).
Tried to delete the local cache (OST), and resync on the same profile, and still. I think the logical next step will be to create a new profile, and again re-sync?
Example of a log (and there are a lot):
13:33:14 Synchronizer Version 14.0.4760
13:33:14 Synchronizing Mailbox 'Omri'
13:33:14 Synchronizing local changes in folder '¿¿Sent items'
13:33:14 Uploading to server 'Server2008.Energotech.local'
13:33:14 Synchronization of some deletions failed.
13:33:14 1 item(s) deleted in online folder