I was wrong. It worked for two or three internet pages, only. Now, it the same like before. I will try to get a new SIM card from Vodafone.

So we have similar experiences... try a sim card from different provider for longer time, I've exchanged my sim card for a new one and it changed nothing...

Maybe anyone who reads this has any idea how we could debug it without help of network operators? I tried checking dbus messages etc. or finding log files on the device last year, but found nothing interesting...