It depends on many factors.
First let's dispense with the encryption part. Encryption has nothing to do with recovery. Whether the content can be decrypted is a function of key recovery but has no bearing on recovery in itself.
Plain text messaging is not encrypted.
Recovery can be complicated or dirt simple depending upon details of the system:
Are you attempting recovery from an end-device, i.e. a phone? Depending upon the phone and the text message app, it could be simple or impossible if a secure wipe was performed. Contrary to one of the comments, Flash storage does not necessarily physically delete the data, that would be a TRIM function.
Depending upon the system, messages may have gone through a central server. In that case, an entire history of messages could be sitting on the server waiting to be pulled off.