Hmm, could they use on-the-fly encryption/decryption? That is, use a symmetric cipher to encrypt the stored data on the servers and then do a simple backup of the data. When you delete your account they would just delete the encryption key. Backing up the encryption key could be done on your side (send you your own encryption key if you need to recover your data).
we're going to offer that.
I think the worry was actually, "Isn't my data backed up somewhere even if you delete it the instant I tell you to? So then you still have my data?"
bingo.
If they can delete my data on the instant -- then they quite possibly don't have backups. If they do have some form of semi offline backups - then not all of my data is deleted on the instant.
Not a worry so much as a harder problem that sometimes doesn't get considered.