Don't do business in the EU if you don't intend to respect the laws. I find the word 'overprotective' out of place in your comment, it says that you feel that once someone gives you their data it is yours to do with as you please.
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.