I heard that they are permanantely stored on a hidden memory chip on your phone. They are also stored on a remote computer at the other end of the network for up to 5 years. The facts were in the paper when that Becks Sex Text "scandal" came to light.
It is true that your service provider logs all text messages for a period, in case the police need to see them (but only in the investigation of a crime and i think they need a court injunction/warrant to do so). I seriously doubt the phone will keep the messages though as memory is a precious resource.