If you're absolutely certain that the user's identity cannot be reconstructed from the remaining data points, then yes, a full anonymization is enough. You are, after all, removing personally identifiable information, even if the record structure remains in your database.

It's a law, not a technical constraint. No one gives a fuck about some foreign key relations, they care that personal data cannot be accessed, or somehow reconstructed.

This may well be harder to get right than just deleting the data. Just as in the saying (and this is a terrible paraphrase) goes:

  "Anyone can design a lock that they themselves can't pick"

If you think you have anonymised data sufficiently you may well not have done it sufficiently to prevent others from re-conctructing it:

https://en.wikipedia.org/wiki/AOL_search_data_leak

Yes, but this is actually more difficult than you think. It doesn't take very many data points to ID a user.

Anonymizing like that would be GDPR compliant yes, as long as the remaining information absolutely cannot be used to identity the original subject.

That it isn’t known with confidence is your answer to whether it is worth implying it is easy.