If a user's data needs to be deleted for whatever reason, simply discard the user's corresponding encryption keys. That way you can effectively wipe the user's archive without needing to touch the tapes themselves.
(Whether German data protection law applies in Google's datacenters is a wholy different story though.)
Otherwise, any kind of backups would be unlawful for a company.
I think this may have changed since that talk. I think Google still doesn't technically guarantee full deletion (who knows if someone's GC process messed up or has a bug) but in practice it happens, at least AFAIK. It is expensive. And it does take time, I wouldn't expect all my stuff to be purged until at least 180 days (the 90 days they are supposed to delete after + ~90d for the delete to fully propogate).
It also drives every engineer nuts when they're asked is your service wipeout compliant and they realize omg I can't store this data longer than x days?! shit shit shit
European Privacy Shield compliance is yet another bag of legal worms every service has to deal with. More deleting, encryption at rest, etc.
Your data may still live out on some server - but it is effectively unrecoverable.