It is not an easy thing to do you need software to be able to read message bytes on the SIM card. It's not something everyone does - more likely to be done by police forensics looking at criminals phones : )
When you delete a message it's status byte is set to delete. The message is still present. The message 'slot' however becomes available to the phone for storing a new message.
You can change the status byte to one of the other settings and the message is recovered. - If the slot hasn't been overwritten by a new message in the meantime.
The status bytes are shown below.
00000000 Unused
00000001 MT message, read
00000011 MT message, unread
00000101 MO message, sent
00000111 MO message, unsent
So generally I would say no you can't unless there is something really valuable in the message worth the hassle.