It's simple: you don't get to store data unless there's a technical requirement to keep that data stored to provide whatever service a user signed up for.
If a user didn't agree to their data to be stored in the first place, you don't get to retain it at all.
Whether you can discard data about a user "against their wishes" is likely covered by your terms of service. If you're a commercial hosting provider, there's probably a higher barrier than if you're a free doodling website. This has nothing to do with privacy, though.
If a user tells you to destroy their information, you need to destroy all information about them. There's obviously some wiggle room (e.g. if you keep a flat "view count" on an article, there's likely no way to argue that you should have to deduct the user's views but if you're keeping a record of "views" linked to user IDs the user ID may still be personally identifiable if it can be correlated with other data).
But most companies fail at deleting even the most obvious data. If you "delete" someone's account and they're unable to sign up with the same username or e-mail address again, you're likely not properly deleting information.
And that's if you even offer the option of deleting an account at all. It's horrifying how many (especially American but sometimes even EU) websites don't offer any such option at all or even simply offer an option to "close" an account, marking it as disabled but still retaining all data forever.
> Could I demand that the city/town/council/etc delete all footage of me ever?
Yes. Security cameras have strict regulations and generally recordings have to be destroyed eventually unless there's a good reason to keep them (e.g. they're part of a criminal investigation). This even extends to police cameras: if a police officer makes a recording (e.g. at a demonstration) and the recording isn't relevant to any investigation, you can ask for it to be destroyed ASAP (rather than waiting for them to destroy it). This also extends to other information like your name and address.
> I could commit fraud or launder money, and then demand that my bank destroy the evidence.
There are special laws for financial transactions and criminal investigations. There is such a thing as a "permanent record" but it is clearly defined what goes on it and what doesn't (and at what point it has to be destroyed). There are also very strict laws for handling such information, similarly to the strict PCI rules for handling credit card information.
You're basically arguing that privacy is a slippery slope but in reality it isn't. Privacy may be an "unnatural" concept but the expectation of privacy is a human right (like, officially, as part of the UN Declaration of Human Rights). The EU actually has very few "absurd" policies -- most of them only appear absurd when taken out of context. I assure you that EU privacy laws are not part of them.
Except for the cookie notice. That's not only ineffective but outright ridiculous.