Each of Reddit’s listings (top submissions, recent comments, etc.) is generated from a database index. Those indexes are limited to 1000 entries, by dropping older ones as new ones arrive, and they don’t re-index for deletions.
That means that once a listing goes over 1000 items, the oldest items can no longer be found through it. The messages are still in the database somewhere, but can only be reached from some other index (different sorting order) or a search or a direct link.
So, the messages are not being deleted and then restored; they’re not being deleted in the first place, because the tools have no way to find them.
This is why a formal data deletion request is often more effective than a deletion tool on Reddit.