Hi Nico
One day after that (today morning) I was called back, re-explained the issue and stated that I think that the nat is the problem. Took me about 10 minutes arguing that this in not Linux' fault. Then he send me a useraccount/password/apn to use for testing and I should give him feedback in a few days.
Never tell the support you are using Linux :-) They follow their scripts and can not handle such "exceptions". We are all clever enough to lie a little bit :-)
Nice weekend, Reto