It seems like I did solve my problem, but I have only a faint idea about the why.
My setup is the following : my router (fritzbox) connect to the internet and my core is connected directly to that. Ever since I'm using Linuxmce I used a static IP-address for that connection. As I found out some weeks ago, I made a mistake about DNS- it was set to the IP of the router instead of the core, but it was working. When I found out my mistake I changed the settings for the DNS to the IP of my core, but left everything as static.
I did some checking on my router and found a setting for the dhcp there to always assign the same address to the core. Now I went to the core and changed the network setting to use dhcp, which in theory wouldn't really have made much of a difference. Imagine my surprise, when I checked in Freebpx to see all my Phones online and working.
The only two problems I have now is that somehow surfing is a bit of a drag, since I have to request every page at least twice before the page actually loads, nslookup returns first a timeout of 2 seconds and then gives a result. The other problem is, that I cannot connect to windows messenger anymore.