lo más probable es que no haya vuelta a atrás... si tienes un telefono de los viejos, pierde toda esperanza... si es android o smartphone podría requerir root y un analisis de bajo nivel... esto si la zona de memoria no ha sido sobreescrita
en tal caso los mensajes se guardan en una db tipo sqlite en
/data/data/com.android.providers/telephony/databases/mmssms.db
pero si están borrados tendrás que tener suerte para poder reconstruir la estructura... ojo, ni por accidente es trabajo facil y profesionales te dirán usualmente que no