should
See RFC 2119, "should" usually denotes something as "optional"
But really, almost zero companies build software around data in such a way that the data could and will disappear at any moment.
Regardless, in practice, billion dollar companies have the resources to ensure 'delete' isn't actually "partially hide for years/forever". With proper surrogate IDs they could even preserve a minimal amount of meta such as tombstone IDs to ensure all first and third party systems are in compliance.