One thing about GDPR that I've never heard answered convincingly - when a user requests deletion of all of their personal data, does that include also any history of the deletion request itself?
There are several possible legal bases for processing personal data and legitimate interests is one; if legitimate interests wasn't your reason for processing personal data in the first place, then you couldn't rely on it later.
If legitimate interests were the basis for your processing, and a person requested their data be deleted, you have to be able to demonstrate that your legitimate interest overrides their rights. You should probably also demonstrate there aren't other steps you could reasonably take, eg partially deleting or anonymising the data.
I didn't save the link but at least one country's privacy regulator has said that when processing a deletion request you do not have to go through all your backups and remove the data from them too.
If you ever have to do a restore from those backups you will need to re-apply past deletion requests to the restored data before you start using it.
But honestly this is a very minor point, if that's what is keeping you up at night, you are amongst the most compliant ones !
GDPR is mostly about processing user data, not storing them. So user can execute "right to be forgotten", so the data will not be accessible in any way and you are not allowed to process them, however you have full right to keep those data if you believe that this user might show up five years later and try to sue you for a, say, undelivered order, etc.
In that particular case you need to be able to prove that user wanted to delete the data. Otherwise user might sue you that you've deleted those data without agreement and caused some business losses in that way.
Someone third party might also show up and accuse you that you deleted data as a part of conspiracy with the user (think of angry former wives/husbands).
Storage is considered as processing.
But yes, you're right that the Right to Erasure is not absolute.
If you use it to block the user from using your service or punish them in some other way, that might be very problematic in legal sense.
PII is a US legal term and means precisely nothing in the context of the GDPR.
When you receive a deletion request, you must delete the data and stop using it from anywhere you don't have a legitimate reason to continue processing it under one of the reasons for processing personal data without user consent.
Which is easier said than done, because it's against general development practice of having a single copy of any data that you use everywhere without much checking. Instead, you have to either check a flag before using data (do I have consent? Has it been revoked?), or keep several copies of the same data for distinct use (for example, one copy for your app, one copy for legal reasons). The first approach helps you to be able to prove consent. The second approach helps you when you need to archive data past its retention date.
There are also limits placed on this by other laws. For example tax agencies often require companies keep sales records for multiple years. A request for deletion doesn't remove all invoices from sales records with their name on it. I imagine there are more examples, but I think it gives a good indication that GDPR is not where the buck always stops.