If you delete from your "My Photo Stream" you will get this warning. The Photo Stream is automatically synced across all devices using your Apple ID. If you delete from one, it will delete from all that sync to that stream.
If you switch to Albums and select Camera Roll, you will be deleting photos from your iPhones storage only.
Apple doesn't list a required/minimum free space, so you'd need to work with Apple support to get that sorted. As for the cache, you've already done all you can.
iOS has several low storage warnings it sends to each and every app to clean up cached files and with < 500 MB of free space, I'd wager you've exercised those limits continuously and it's surprising to me if this is the only thing that is broken on your device right now.
I would:
- Delete one or two large apps that you know the data is safe/unimportant. Try to get 2 GB of free space if you can but 1 GB of free storage should be sufficient.
- Power off the device and power it on to let system cache files re-generate
- Open photos on the device and on iCloud and see if normal operations resume. I've had good luck with photo libraries coming back from all sorts of intentional abuse like you've unintentionally performed. It can take 24 hours or more (if you hit any upload limits) for the cleanup script(s) to trigger so you might wait 48 hours to see if the added space lets iOS complete the upload work that is queued.
Also, Apple does offer debugging profiles for iOS cloud sync if you call in for support and if their "cookbook" method doesn't yield results. If your case get escalated to engineering specific error messages contained in the debug logs can often assist you in further diagnosing why all the photos are not syncing.
You could also just push the photos to a computer or other iOS device using AirDrop or USB and upload them to the cloud from another device and then remove iCloud Photos temporarily from your iPhone to allow enough space to resume normal operations and then re-enable the library with the option to reduce file size.
Basically, the system is designed to stop working when there isn't enough space for temporary files to work. This is the same design as OS X and other unix in general.
These operating systems use free storage space to cache things and make your experience better by accelerating slow resources like network and CPU by saving work when it's done to reuse it later. When you deprive the system of that buffer, things slow and eventually stop.
Best Answer
Yes, your iPhone will remove originals that you have not browsed recently, and then re-download them when you next look at them. If you want to learn more about it, lookup a cache. With the new Photos app, the originals are stored in the cloud, and the images on your phone are just a cache. (Except that when you edit a photo in the cache, Apple preserves both the original and the edits in the cloud.)