swamphox Brick and mortar type places or by mail?
I think there aren't many forensic recovery places, so for most people they would be by mail. Whether you live near a good repair shop that is willing to try to retain the data (some of them wipe all devices by policy), I don't know.
If you are thinking of suing somebody, which will inherently cost a lot of money anyway, paying a forensic recovery shop something to increase the likelihood of recovery might make sense. In the other direction, your attorney might advise you about the feasibility of obtaining the messages via discovery.
Overall this might be a good time to stop and discuss with your attorney.