写真を全て削除してもストレージに写真のデータが残っている

そこではなくて、設定＞Apple Account>iCloud>ストレージでしらべてみるとどうでしょうか？

デバイス本体のストレージと iCloud ストレージの違い - Apple サポート (日本)

ご使用のiPhoneに写真データが残り続けており、削除できない場合は、iPhoneのバックアップをとってから、リセット（初期化、全てのコンテンツと設定を削除）した後に、バックアップからの復元を試してみて下さい。

iCloud写真を使い始める前に撮影したデータが残っているのかもしれないです。　不要なら、削除して下さい。

そうです。　『最近削除した項目』の中も削除します。

他にiCloudのストレージを使うものがあるからでしょう。　ご自分で調べて下さい。

そうです。　写真のデータはゼロではないでしょうか？