iCloud Photo Library Deleted Photos Reappear

From time to time photos that I delete will reappear in my photo library. I’ve heard that if you have “My Photo Stream” turned on this maybe the cause of this. I have four Apple devices: iPhone, iPad, iMac, and Macbook Pro. I’ve verified it is not enabled on any of the devices.

When deleted photos reappear they appear at the bottom of the album “All Photos” on my iPhone and not sorted by the date of the photo. This is really the only way I know that deleted photos have reappeared.

Does anyone know why this happens if there is a solution? I try to keep a very manicured photo library and its frustrating to have deleted photos reappear.

Not sure about that specific issue buy FYI on the Mac you can

View > Library > Recently Deleted

and in the upper-right of that window is a Delete All button.