It's different for every service. I use Skydrive, and I'm pretty sure if I delete a file on my computer, it goes to the recycling bin on all of my computers, as well as a "recycling bin" on the Skydrive cloud. I don't know how long Microsoft holds onto the data, but as a rule data storage is cheap compared to the other costs of running a datacenter.
Learn something new every day.
Paranoia.
I meant real reason.