Just want to add a recent experience I had on this issue. I accidentally deleted a bunch of photos on my Mac (including from "recently deleted") and didn't realize it deletes it from my emtire iCloud photo library. In a state of panic, I contacted apple and they were able to restore all the photos that were "permanently deleted " from the last 60 days. This surprised me quite a bit as I was not expecting them to get them back. Makes me think if any pictures on the cloud are truly deleted.