If you did nothing with MyPhoneExplorer since you deleted the messages you have a chance cause the datafile is saved on closing the program (or if you refresh). What did you since deleting ?
Most important is to save the file (to another location). THEN close MPE and copy the saved file back to the previous location. Start MPE again. Hopefully this works...