if it is anything like deleting something on a pc they dont go anywhere it just destoys the path to the file so the phone sees that allocation space as empty and therefore overwrites it (i think)
Atkins - I just answered it. They stay in the memory. Jetboy's right too. I read an article a couple of days ago, in The Observer, I think, amongst other things, it was about how the police solve crimes with the assistance of text messages which people think are deleted.
thewillow that is slightly different and i am told is because all messages go through a relay station which takes a copy of the message (for criminal/legal purposes). When you delete a sim entry then correct the phone just loses the entry on the sim, but the sim memory addresses are not wiped i believe, so the entry remains there until it is wiped over by a new entry