Do you exchange photos and videos via iMessage? When m son was first born my message storage was huhge despite the 30 day delete being on but it was just because I was sharing a lot of photos and videos.
If that's not the reason then you can set up the phone again and restore the backup and see if that helps.