registration times out all of a sudden

I’ve had Asterisk register with for a few years now. All of a sudden, a few days ago, registration does not go through any longer.
It times out with reg_sip_timeout.

I can register directly with SIPGATE using a softphone.

Has anybody seen this as well?

One additional aspect I’ve never had to consider: Is there any way (do I have to) account for the fact that the sipgate servers are oversees (from where I am trying to connect). Pinging, the registration domain, takes around 180ms, while a close by server for another trunk is around 20ms.