where do your deleted messages go?

There is no trash for text message. Once you delete it, the text is gone.

the only way to retrieve them is to restore from your backup if those text were included. http://support.apple.com/kb/HT1766

Aliens maintain a massive server on Mars where this "trash" is deposited. They then collect these deleted messages & read them for entertainment on their way home 😎.