I used to give lectures in forensic computing. The G1 doesn't have a deleted items folder for text messages (although perhaps some replacement Messaging apps do - I've never looked, but you would have needed to install it before you delete the message).
As such, it is deleted from the database on the flash memory. This is very similar to when you delete a file off any drive. The data is not overwritten when it is deleted, but simply marked as free space. It can be overwritten very quickly (fractions of a second) if something needs that free space, or it can hang around for days.
It would be possible to recover such deleted data using the correct software on a rooted phone. You could run the software safely from SD card without risk of overwriting the "free" space that contains your messages.
If the phone wasn't rooted, then you can make an exact copy (image) of the flash memory using the correct hardware (this involves opening up the phone and connecting a piggyback flash driver IC over the top of the flash memory ICs). This isn't the kind of stuff the general public can do, or anyone without a decent electronics background. From then on you can analyse the data however you like, and possibly recover the data if it hadn't already been overwritten.
Finally, if I recall correctly, the last few (4?) text messages are stored on the SIM card, so sometimes it's just a case of popping your SIM card into an old phone that doesn't use its own memory for handling the SMS messages and just reads them directly off the SIM card. Most Nokias from 10 years ago did this. There's also hardware around that can do this.
In terms of truly deleting text messages, forget it. They're all stored somewhere. I see SMS evidence used in court cases frequently, sometimes dating back to the mid-1990s. I would imagine every text message ever sent is archived somewhere. Think about it - the US sent around 1 trillion (1,000,000,000,000) text messages in 2009. Let's say the average length of a text message 40 characters. So that's 40TB of data. Now consider that with compression it'll go down to around 1/80th of that size. That means you can store every text message sent in the US in 2009 on a single 500GB hard drive.
