You have to have software to recover them but on the Captivate you can go to Contacts then at the top press History and it will display Calls, Messages, Etc... But on the messages that are deleted it will only show the title but that tells a little bit...
Do as hang says and contact your carrier. They keep copies of every text sent and received for legal reasons. Ie, the police suspect the phone has been used to traffick drugs. They would get a warrant and the carrier would supply them all the messages.
They can resend them to you if you request it, so long as you can prove your identity and ownership of the phone.
Do not call a third party company, they more than likely can't help, and quite possibly steal your identity. I repeat, do not trust third parties.