Hi ntilly,
I have read over your comments and the replies to them from my Very Good Buddy Pat. Not surprising, being that Pat is a Level 4 SIM Forum Grand Master 🙂, his recommendations are, IMHO, prudent and sound.
I have a couple follow-up questions. Perhaps you already answered these. If so, I apologize for missing them when reading your comments.
1. Are you using a new 128K SIM card in your iPhone 4S? Or, are you using a SIM card that was used in a former phone? I mention this as there is quite a bit of empirical evidence that the iPhone 4S, coupled with the iOS 5.1 update, REALLY "WANTS" a 128K SIM card. Even if you do have a 128 SIM card and it came new with the phone, I would get it replaced with a totally new 128 SIM card as it may have been corrupted. Replacing the SIM, as Pat said, is relatively painless and free. So it is a wise first step in this next phase of your problem solving.
2. If replacing the SIM does not work, ABANDON SHIP! Pat is right, after trying a new 128K SIM and meeting failure...get your phone replaced. Pat is an expert at this. In fact, he may hold the Guiness Book of World Records on replacing iPhone 4S's. 😁 If replacing the SIM does not work you have pretty much exhausted all reasonable tactics at getting your phone back to working order. Pat is right again, if you live relatively near an Apple Store that would be the place to go to get a replacement phone.
If you go to the Genius Bar at your Apple Store, you may find that the Genius is not as up to speed about this SIM issue as you would hope. If that is the case, you can refer him to this link:
http://support.apple.com/kb/TS4148
It is an Apple Support document stating that iOS 5.1 is the recommended solution for these SIM problems. Since you have iOS 5.1 installed, you could refer the Genius to this link as a way to convince him/her that you have already followed through on the Apple recommended solution and it failed. Thus, it is time for them to give you a new phone and not waste any more of anyone's time.
You could also refer them to the link to this forum. 85 pages filled with complaints and stories of SIM suffering should further convince them that their best course of action is to get you a new phone. You can also mention to them that this discussion forum is not the only forum about SIM problems on the Apple Discussion site. There are quite a number of other discussion forums centered on this same problem.
Of course, maybe replacing the SIM will work. That would be nice.
Lastly, the fact that your SIM worked in a different phone does not guarantee it is not the source of your problem. Was the other phone an iPhone 4S? As I mentioned, the 4S seems particularly sensitive to what SIM you are using.
OK, good luck. We are all pulling for you and hope that you can report back with good news.
Best regards, Mr. Luigi