Hi magazan,
Your situation is unusual.
Unusual because from postings in this forum it is not common to see an iPhone functioning properly through all this mess that started when the iPhone 4S was released last fall and THEN start to show the SIM problem almost 9 months later.
It appears you have tried all the less intrusive stratagies that have given some users relief. The only missing thing you could do (which I do NOT recommend doing right now as it is quite time consuming) is to first backup your iPhone and THEN do a reset. I won't go into the details of this right now b/c, as I said, it would not be my choice for a next step.
As unusual as your situation is, some things are relatively common and I believe help us to chose your next step. For reasons I do not know, Orange has been mentioned in this discussion forum quite a bit with regard to SIM problems. I do not live in the UK and am not familiar enough with Orange to know why this is so. But, those Orange customers who have had SIM problems have frequently found relief by having Orange swap out their current SIM card replacing it with a NEW 128K micro SIM card. I know. I know. You have heard this a 100 times. But, the fact remains that the iPhone 4S is very particular with regard to the state of affairs of the SIM card being used and what type it is. I don't know how old your current SIM card is. Was it brand new when you bought your iPhone 4S? Was it transferred from a previously owned phone? No matter, SIM cards do go bad and it is possible that has happened to yours. I would go to Orange, explain all you've already done to troubleshoot this problem, look exhasperated, explain that other Orange customers have solved their problem by replacing the SIM card (use this forum as proof although hopefully that will be unnecessary) and stand your ground until they replace your SIM card with a brand new 128K micro SIM card. I am sounding a bit defiant and aggressive here and I don't want to imply that you will have problems getting Orange to replace the SIM card. Much more often than not things have gone smoothly with Orange. But, you may get a salesperson on a bad day. Don't take no for an answer.
If that doesn't work, then you really need to start to suspect your iPhone and it would be time to ask Apple for an exchange. You could mess with this problem forever and that is not fair. Take advantage of Apple's reputation for good customer service and get a replacement phone. You are clearly within your 1 year warrantee period.
But, because replacing the SIM card is relatively painless I would absolutely go that route first.
By the way, you mentioned the hope that someone from Apple is monitoring this forum and might post a coherent reply or response. I have never seen that happen. I am sure Apple has their reasons for pursueing this strategy. I am pretty sure I would not like their response! Be that as it may, these forums are for Apple users to share their experiences and for other Apple users to offer assistance if they can. Obvioulsy, someone from Apple is monitoring these posts. I am sure if I unleashed a tirade of ungentlemenly language here, the post would be removed by a moderator from Apple. But, that's the extent of Apple's involvement as far as I can tell.
There is an Apple Feedback site where customers can share concerns with Apple. I don't think that would be of much help to you in this situation since the SIM problem appears to be relatively conquered as of this date. However, for future use, this is the link to the feedback site:
http://www.apple.com/feedback/
Please do let us know how things turned out for you as that would be of help to future users of this forum.
And Good Luck! Mr. Luigi