It may be technically difficult / expensive / annoying if it was not designed into their system. Your linux box doesn't has hordes of peers / backup mechanisms and cross references to users, to a point that it may be impractical or not cost effective to conclusively prove that a user is deleted everywhere
Deletion may not have been in the original spec or in any of the specs that were bolted on.
No one said backups.
Deletion of the account should be as simple as overwriting a row on a few tables. If they can handle authentication process, disable accounts based on some automated processes, deletion or the process equivalent to it is similarly possible.
Even in case of backups it can easily be done (delete decryption key for this user's row, if you planned your backups right), but even if it isn't (historical backups for example), even the regulator will agree it's fine (BT, dt).
Sure, ok. But whatever happens is still an internal process. Not a legal one.