I can think of an obvious way to handle this:
Step 1: when backing up a user's data, encrypt it with a unique key for that user.
Step 2: when a request-to-forget comes in, delete the key.
Your backups will remain immutable but the user's data is inaccessible.
Of course you'll need some system to manage all the encryption keys and that system is going to need its own backups, so this isn't a completely trivial solution, but encryption keys are small and it should be much easier to design a non-immutable backup system for them (especially since the keys themselves aren't PII, and you don't need to keep historical backups of them, just backups of the currently-valid set).