Well, now after I've been researching this problem with various friends of mine, I heard another variant of this: I'ts not "DEMAGNETIZED" as the people from the Orange Store told me, it's just FRIED, the chip inside the SIM is fried or dead or whatever. I insert the SIM in another phone, and still the same "INSERT SIM" message (a nokia 1XXX I think, it's a simple phone with just a flashlight).

Read about this on XDA, and almost never was the fault of the phone (my phone never overheated, never drained battery more then normal or stuff like that), so the questions still remain... WHY? WHY DOES THIS HAPPEN?!

Correct, that's what a friend of mine working for Vodafone said to me.

Now here's his variant of the story: The SIM is like a fuse for the antenna, so if there are some frequency fluctuations the SIM card is the first one that gets fried just to protect the GSM Driver (chips or whatever). He told me that once a customer came with a FRIED (but the good kind of frying, that the SIM was physically burnt, with visible marks of burning) SIM card, they replaced the SIM and the phone worked beautifully for 2 more years flawlessly until the customer came to get a new phone.

Now still the questions remain, why this RANDOM breakdowns of the cards?