Ok, I've done some extra testing and I have found that's an iOS 8.x / iOS 9.x bug. I was wrong before, it also happens with videos: I don't have any video in my iCloud Photo Library but I have several in Masters folder.
Steps to reproduce on iPhone / iPad (same with videos):
- Turn off Wi-Fi.
- Shoot two photos.
- Delete the first one and leave it at Recently Deleted album.
- Delete the second photo and delete it from Recently Deleted album too.
- Go to Settings > Photos and Camera. You will see it says something like "Required Wi-Fi, 2 photos pending upload". Notice that it says two, instead of one.
- Connect to a Wi-Fi network and let iCloud Photo Library update.
- Go to your Mac, open Photos and you will see only one photo in Recently Delete album (the first one). Delete it permanently.
- Go to Finder, find your iCloud Photo Library > Show package content > Masters > 2015 > 10 > (day folder) > 201510(day)-(time). You will see the second photo, supposedly deleted permanently from iCloud. But it wasn't, because the iPhone uploaded it anyways.
When you do the same but connected to a Wi-Fi network, it works fine: when you delete photos from Recently Deleted album, they are deleted from iCloud and from the Masters folder.
I don't know why, but when you delete photos or videos from Recently Deleted and iCloud Photo Library is not up to date (because you are not connected to a Wi-Fi network, for example) the iPhone keeps them in his memory and then uploads them "invisibly" to iCloud. So the workaround is shoot photos / videos, delete those you don't want to keep, but not delete them from Recently Deleted iOS album until all of them are uploaded to iCloud.
And I don't know if these "deleted" items are wasting iCloud storage. I don't see an easy way to delete them permanently, because they don't show up anywhere besides Masters folder. Maybe removing directly from there?
I'm going to submit this bug to Apple; I will keep this thread updated.