If you are using a Nokia phone, then you can easily recover deleted SMS messages from your device without any data recovery software. You just need a simple software FExplorer, you can download it for free from here. Follow these simple steps to recover deleted SMS messages:
Step 1: Download and install FExplorer in your device.
Step 2: Open FExplorer and go to C: (If you use phone memory to store messages) or E: (If you use memory card to store messages).
Step 3: Now go to System -> Mail.
Step 4: Under Mail folder, you will find some folders which are named like 00001001_S
Step 5: Some files are there under these folders named like 00100000. These files are actually your deleted messages. You can view these files with the help of text editor/viewer.
Note : This trick may not work on S60 3rd edition phones. I have tested this trick on S60 2nd edition phone.