Well... We're missing some info here. First, what app are you using for SMS? Some SMS apps will archive messages, rather than delete them. For instance, the Google Messenger app, if you swipe a message away, it gets archived... and most likely removed after a period of time. The app you are using might have a similar function.
Did he look at YOUR phone, or his current GF's? If you delete a message, it doesn't touch the message on the other end...
If an SMS is truly deleted, there's really no way it can be retrieved... unless there's some archive at your carrier and there's a court order to access them (which I assume is not the case here).