"even if they say they did, some middle manager probably "forgot" to also remove it from the back up system. Yes, the data is off of our servers.... You didn't mention tapes..."
And even if they could prove all your data had been deleted by them from all their servers and backups, How about those third party partners they've shared (sold) your data to prior to deletion?