Well, you are right. Looks like the problem is not with authorization
but in the line
Contact: <sip:gw+1.2.3.4@5.6.7.8:5080;transport=udp>
that the gateway would like to see as
Contact: <sip:username@1.2.3.4>
I've found (almost undocumented) parameter extension-in-contact, but
it still gives
Contact: <sip:username@5.6.7.8:5080;transport=udp>