I use an online backup system from LogMeIn called Cubby for my personal stuff.
It makes an initial copy, that took a while for my huge folder, then only copies changes thereafter. When I delete a file I can go to Cubby and the file is gone. I can go into archives though of Cubby and find the last 15 changes I made. I can retrieve a deleted message.
The downside with using it here is to un-delete this many messages could take a very, very long time.
I am going to look into an online storage area that lets me xcopy to it but it doesn't copy any deletes. It will overwrite any files but that is ok in this case. I will only use it for II.