You don't necessarily have to delete stuff from cold storage right away. You just need to have a process to remove deleted PII when you retrieve/rewrite your backups.
But remember, strictest interpretation wins.
As far as I can tell to comply with a deletion request with absolute certainty requires infallible storage (which would remove the need for backups) or modifying backups (which contradicts the concept of a backup). Maybe you can claim 'force majeure' at some point, but perfect compliance seems impossible.