OT: I saw a similar thing (deleted messages returning) in Messages on MacOS a couple weeks ago, shortly after I upgraded to Monterey. A whole bunch of deleted messages from 2017 through 2019 returned. Nothing from earlier or later returned.

I mentioned this on Reddit and someone replied that they saw it too with hundreds of deleted messages going back to 2015 returning.