They're in a database file. You have to root the phone, then install a SQLite editor, then learn SQL, then look for the file with the editor, then figure out exactly how messages are marked "deleted", then run a SQL query to undelete them.
In other words, for all practical purposes, if you haven't backed them up, you can't.