Für diejenigen, die eventuell ein ähnliches Problem haben, des Rätsels Lösung ist zwar nicht gefunden, aber dennoch eine Abhilfe:
Man gebe als Serververbindung einfach anstatt: sip-gmx.net
sip.gmx.net an. Klar, nun könnte man sagen, ist ja super, dann funktionierts immer. Tuts aber eben...