Erase the name and address fields from the user in the database. You don’t have to delete any line, and that person doesn’t have any personal info in your database anymore. Problem solved.
Anyway this stuff is super complicated and there's no rollback for data that was mistakenly deleted and shouldn't have been, so the point is there are layers and layers of complications and scenarios and it's not as simple as everyone likes to make it out to be. It's not impossible, but it's definitely a lot of difficult work.
The "right to erasure" isn't as strict as the "right to be forgotten" -- You (the end-user) would need to prove that merely having your name and address in billing records violates your right to privacy. And to make that argument you'd have to provide evidence the business is using said information for purposes other than billing.
Personal data can be used lawfully to "fulfill contractual obligations with a data subject" (eg: fulfilling a purchase, and retaining information for warranty/returns/RMA etc purposes) and "To perform tasks at the request of a data subject who is in the process of entering into a contract with the controller. " and "For the legitimate interests of a data controller or a third party"
And what if the PII is stored in a blockchain? Then what?
No clue. But I can't wait for that to be tested, because I'm very curious what the solution will turn out to be.