If they don't delete it and they have European customers they are breaking the law.
PS: Event doing what you propose "less lobbying, less money in politics" would require lots and lots of lobbying (as this is the current system).
It doesn't seem like laws specific to some European country should apply anywhere outside of that country. I can maybe see the EU(since they like to apply laws everywhere).
You did call them 'customers', which means there's an exchange of money. Is there a restriction on European banks to prohibit them from dealing with sites that don't comply with the country's law?
As for laws specific to a country applying outside it: you can do whatever you want but the moment you hold assets abroad or intend to travel you are exposing yourself to potential legal action, something always good to keep in mind. The United States has a long history of enforcing its laws outside its borders.
Also, you are wrong about how you'd go about implementing such deletion. You don't need an 'is_deleted' flag at all to keep your foreign keys valid, all you would have to do is to overwrite the record with random data or blank the personally identifiable fields and delete anything that that user has given you. That's not that hard and purposefully mis-implementing that would not look very good if it ever came to a lawsuit. Pro-tip: consult with a lawyer versed in the matter if you want to do this stuff at all it is better to do it by the book.
"Keeping foreign keys valid" is not an excuse to break the law.
A lot of Japanese sites IP-ban foreigners so they don't have to deal with them. I always figured, why not leave the site open for everyone but not officially support them? I guess putting technical measures in place prevents having your assets seized, or being sued or arrested when you step foot there.
If an EU customer with data retention laws uses a VPN to bypass an IP-block(and pays with bitcoin or something), would you still be subject to their laws? Or would the attempt to block them be sufficient legally?
This sort of behavior is exactly why the industry is no longer self-regulating but is now forcibly regulated in the EU. And soon to be much more forcibly regulated, come 2018 the new version of the DPD will come into effect which has much more teeth because there are still plenty of companies that are trying to evade their responsibilities. For instance, from then on, if you have been breached you will be required by law to report the breach.
So, be nice to your users, respect their data and try to be better than your competitors rather than to find ways in which you can creatively evade legislation that is especially meant to apply to you and your customers.
If they use it, they're the ones breaking the agreement.
Not sure what would happen though. If they sue you, you can probably sue them back. But not sure what you would end up needing to do.
To me, the troubling factor is that the EU hasn't clarified the law so seeks to apply it to individuals who are not in the EU and never intended to do business with EU residents.
any other identifying information
Honestly though, if you tell users you can delete their data on request, you should just do that - delete all of their data, full stop. If you can't or choose not to, you should just be up front about that, also - that means in plain language they will see, not buried in a TOS or whatever. It's the only ethical way to handle this. National boundaries and jurisdiction are side issues, really.
Not really, at least I've found keeping data much harder than deleting it. The only hard part is backups.
Deleting all data is as you note, easy, with the exception of backups.