Thanks for the hints. I find forcing my phone to 2G somewhat problematic because:

• mobile internet is too slow
• less security than 3G (eavesdropping, ...)

I just cleaned my SIM card (the contacts looked pretty good by the way) and I'll try to reproduce this. If it is still an issue I'll try another SIM card and report back.

Thanks everyone. At least it does not seem to be a common N900 problem