I think it all depends on whether the sms is on the phone or the sim. If on the sim then they can be recoverable as it all depends on what the phone does when you hit "delete". Some phones just mark the block as "free" whilst leaving the data there, like a computer normally does with it's hard disk, whereas others completely remove the data from the sim. It seems that Motorola is one make where recovery is possible.
If the sms' are on the phone memory, then they are gone forever.