If they were on the device and deleted, the carrier/service provider can't help with that. There are some things you can try, but that will usually not effect any lost messages.
While there is no guaranty that you can get them back. Deleted does mean deleted. There are a few apps/programs out there that 'may' be able to help you recover the data.
A few of the programs you could try would be... DiskDigger, MobiSaver, Android-Recovery and Tenorshare. They are all data recovery apps/programs. There are many others out there, so check around and see which you would rather try. There is also one called RECUVA, that I have heard is free, which you could try.
One important note though, most of these programs are not free. They may say they...