혹시 구글포토 등 다른 클라우드에 백업 안하실까요? 그렇다면 몰라도 본체와 클라우드에서 모두 사라졌으면 복원하기 힘들지 않을까 싶습니다.

삭제해도 바로 사라지는게 아니라 30일 정도는 삭제함으로 넘어가서 거기서 다시 복구할 수 있는데 거기는 보셨을까요?

아이폰과 아이클라우드 사진은 동기화 개념으로 둘 중 어디에선가 삭제하면 같은 애플아이디로 로그인한 장치에서는 시간상 차이만 있을 뿐 삭제됩니다.
삭제하면 보통 사진앱에서 최근 삭제된 항목 이라는 앨범에 들어가시면 삭제 시점부터 30일까지 보존됩니다.
만약 그 이상의 시간이 지났다면, 구글포토 같은 세컨드 백업을 확인해보세요.

고객센터에 전화도 해보셨다고하시니, 뭐 삭제앨범이나 기타 애플기기에서 할수 있는 것들은 다 해보셨다고 보면 될것같고... 프로그램 사서 돌리는건 전 효과 본적이 없어서 추천을 못드리겠습니다. 사설 업체를 간다고 하더라도, 핸드폰은 내장 프래시 장치에 저장을 할거고 암호화해서 저장될텐데... 아무리 물리적인 복구 흔적이 남더라도 키체인이 없으면 암호화된 사진을 복구할 방법은 없다고 보시면됩니다. 그리고 현재 그 핸드폰을 계속 사용중이실텐데.. 내장 플래시 장치에서 삭제된 상태로 핸드폰을 계속 사용하면 사진을 저장했던 영역에 다른 데이터들이 사용하게 되면서 더욱더 복구할 가능성은 낮아지죠.
그래서 평소 사진 백업이 생활화 되야 한다고 봅니다. 다른 클라우드 백업이 없으셨으면 포기하시는게 시간적으로나 금전적으로나 정신적으로나 편하실것 같네요 ㅜ

저도 그런 게 염려 돼 구글포토도 병용하네요.

전 예전에 키체인 사라져 버린 경험도 있어서요.