On the Reddit threads, there are also users reporting photos returning after being deleted from a different Apple device of a different type— Even when the original device did not have ICloud enabled.

It's very odd. For it to be a local storage issue, it seems like IOS would have to be copying entire disk images across devices and accidentally doing file carving on freed resources. So I think ICloud is the most plausible technical explanation currently. At the same time, a cloud storage issue implies either malice or incompetence at a level that we currently only have indirect evidence of.