The messages wouldn't be on the SIM, so if they are telling you it is, they aren't giving you the right info. Messages are stored on the phone, and go through the companies servers. The only way they can be anywhere else would be if intentionally saved to them (say a computer or SD card). Not a SIM, since it is only for service, not files.
I would suggest you contact them again about getting copies from their system. They would have them. Even if they say they wouldn't. Now, they aren't 'required' to give them to you, unless you say had a court order to make them. So that part is going to be up to them to agree to help or not.