So, I got a new SIM card, but the problem is still there, unchanged. It's definitely an issue of the phone.

I wonder if it is maybe linked to the problem reported here.

But I do believe it to be a HW problem. I had similar issues with my N900 (see this thread). Finally had to give up on it and bought the N9. And now the same frustration, in less than an year after the purchase.

I have to say that I am done with Nokia. It really makes me sad because I loved both the N900 and the N9. But it is just too much frustration. I will probably send it in to Nokia Service (if there is still a service), because the phone is still under warranty. But I do not expect to get much support. Maybe a Nokia Windows device as a replacement. Will then sell that on Ebay.

I am going to buy an Android phone now. And maybe some day, I will install Sailfish on it.