I presume you're referring to the Short Text Message service offered by
a wireless service provider.  Within that context, no record of any SMS
message is made by the provider other than a summary log entry of the
messaging event - the actual message itself is neither recorded nor
stored in any way by the service provider once the message has been
delivered to the intended recipient.  If the text message cannot be
delivered within the time frame stipulated by system engineers (max
queue time), the message is flushed from the queue and an undeliverable
log entry is made.  Law enforcement can, when necessary, obtain a copy
of the message and log activity for their own warranted use, and would
be the only record of the actual message itself that survived the
successful delivery of said message - and within this context, the
warranted copy is made in real time at the moment the message is
injected into the message spool.  The federal privacy laws and
telecommunication regulations related to this activity are quite strict
and provide serious consequences for violations in both criminal and
civil courts.  Exemptions are allowed in the most restrictive manner
possible for system support functions, and only to the extent of the
intended purpose.  No wireless carrier that I'm aware of actually use
customer traffic for system maintenance activity, preferring to generate
their own test messages which are known to conform to network delivery
and transport requirements at all times.

As far as where a handset stores SMS messages, I'd think they'd be
stored somewhere other than the SIM primarily due to the limited storage
capacity.  If I'm wrong about this I'm certain someone will jump in here
and say so.