Recovery of deleted SMS I have never backed up or sync'd my iPhone 4S and need to recover deleted text messages. 

Are these stored until they are overwritten?  When would the overwriting occur on a 32GB iPhone?
Text Messages are stored in a Database format, and not as individual files.  It's unlikely that they will ever be "overwritten" in the sense you ask, but may well remain in the database tables either forever, or until such regular purge mechanism clears them out on a schedule.

Depending on your OS version, you may be able to open and inspect the files.  See this question for more details.