I thought that's why we have GDPR and similar laws, so you can enforce it? If the company says it deleted your data but it didn't it's definitely not complying with GDPR
There is a somewhat accepted pattern here where backup processes are updated to retain a list of users who have requested deletion, and when a restore from backup is performed, before the restored system is brought back online, the data of users who have requested deletion is removed.
As with many other compliance and governance controls, this is a known pattern, but is subject to review by auditors, and the overall pattern, or the specific implementation of the pattern may not survive a legal test via a complaint by a consumer or regulator.