I did some more investigation. I have a new iPhone SE handy with a new AppleID on it so I could play around with this without worry of losing anything.
So I recorded a 4k 60fps video that was around 2 gb on the iPhone SE. I saved it to photos. As you can see in this photo there is 2.2gb of photos, and iCloud Photo is asking me to turn it on to move that 2gb file into iCloud.
View attachment 1855434
I then deleted the video, and removed it from recently deleted.
View attachment 1855435
Now when I look in iPhone storage the 2.2gb of data is still sitting under Photos. If we look at iCloud Photos now we can see it doesn't have data to upload anymore it just suggests turning it on.
View attachment 1855436
Technically the video is still there but its cached. It will be overwritten by other photos and videos...so lets do that...
I took 50 photos rapid fire.
View attachment 1855437
And we can see that Photo usage is still 2.2gb. However if you look at the iCloud Photo suggestion it now says 513.9mb if I enable it and upload those photos to iCloud.
View attachment 1855439
That 513.9mb is very odd to me. Not sure what would be uploaded exactly because all the photos on the phone are 151.5mb.
View attachment 1855440
However it scales fairly well. I deleted 26 of the 50 photos....
View attachment 1855449
And we are at 234.8mb. So yeah that is a bit weird however notice we are still at 2.2gb.
ANYWAY Long story short, everything is technically fine. The photos app is recording its cache and junk as "photos". The phone will use that storage space for other things if needed. Apple has made if very difficult for the average user to see how much usable data they have though. I think we will eventually see an update to address this, just go back to saying "Other"...