Good investigation. So the problem began between Nov 2011 and May 2012.
I think you're on the right track re: the archive PST and the error. OL might think the archive completes and writes to the sent folder bad data - guessing, but your logic seems good. I stopped trying to figure out why of things a long time ago, I just want to fix the problem and go back to normal.
If the problem is a corrupt store or related to size/number of entries in the store, creating a new store solves that problem going forward. If there is some underlying issue with OL itself, a new store won't help.
At least you know it had nothing to do with moving to Windows 7. MS Outlook forum
Best of luck,