Sorry for late reply. For old data, the easyest way is to burn the tapes and make new backups. Now about new backups, here it becomes nasty as typically they aren't organized granulary enough (but you also need this for exporting the data on user request, so you just need to do it). Instead of backuping the whole databases, backup each users data separately, maybe database partitioning, table inheritance (postgres) or something else, hard to be specific here. Once you did that, backup the data by encrypting them with random key (long enough, we are using 32 bytes of random garbage) for each user while storing those keys on simply modifiable storage, cloud, whatever in triplets. Once the user requests data deletition, just destroy the key. We did it this way and it is great solution (and we DID burn the tapes literaly, luckly we have business data separated physically from everything else from the start).

Logs are destroyed each week and the customer will be notified. Also we anonymize ips and reverse lookups by hashing them, while we still can identify the same visitor.

I hope I was helpful :)