Nat – Asterisk client behind NAT – UDP registration does not work

I have some clients connected to my Asterisk server behind a NAT device. When using TCP everything works OK. If I change the client and server config to use UDP (from transport=tcp to transport=udp,tcp or even simply transport=udp) the phone can no longer register and Asterisk sends SIP: SIP/2.0 401 Unauthorized to the client.

From what I have read it is possible to use UDP behind a NAT with Asterisk, however experience seems to dictate otherwise. Have I missed another mandatory step or is there something else that I am unaware of?

To clarify: it is the clients behind the NAT device; not the server.

Here's the relevant portions of my sip.conf:

[general]
context=bogus
allowguest=no
allowoverlap=no
bindport=5060
bindaddr=0.0.0.0
srvlookup=no
disallow=all
allow=ulaw
alwaysauthreject=yes
videosupport=yes
canreinvite=no
nat=force_rport,comedia
session-timers=refuse
localnet=x.x.x.x/255.255.0.0     ; blanked out for serverfault
tcpenable=yes                    ; Enable server for incoming TCP connections (default is no)
tcpbindaddr=0.0.0.0:5060         ; IP address for TCP server to bind to (0.0.0.0 binds to all interfaces)
transport=udp,tcp

[my-codecs](!)                    ; a template for my preferred codecs
        disallow=all
;        allow=ilbc
;        allow=gsm
;        allow=g723
        allow=alaw
        allow=ulaw
;       allow=g722

[basic-options](!,my-codecs)                ; another template
        dtmfmode=rfc2833
        context=internal
        type=friend


[natted-phone](!,basic-options)   ; another template inheriting basic-options
        directmedia=no
        host=dynamic
        transport=tcp,udp

[101](natted-phone)
callerid="Office"
secret=12345678901234567890
context=internal
mailbox=101@main
transport=udp,tcp

UPDATE: On investigation I have found that this only seems to affect Avaya handsets. Other softphones connected to the same server do not seem to suffer this problem. Here is a sample of register and un authorized packets:

asterisk*CLI> sip set debug on
SIP Debugging enabled
<--- SIP read from UDP:x.x.x.x:1032 --->
REGISTER sip:asterisk SIP/2.0
From: sip:2003@asterisk;tag=46c2abf4589053ec5895ffc0_F2003192.168.0.174
To: sip:2003@asterisk
Call-ID: 1_5a7d0-b0875cb5895fbc0_R@192.168.0.174
CSeq: 1 REGISTER
Via: SIP/2.0/UDP 192.168.0.174;branch=z9hG4bK1_5a7d12149bcad5895ffc4_R2003
Content-Length: 0
Max-Forwards: 70
Contact: <sip:2003@192.168.0.174;avaya-sc-enabled;transport=udp>;q=1;expires=900;reg-id=1;+sip.instance="<urn:uuid:00000000-0000-1000-8000-2cf4c54ef19b>"
Allow: INVITE,CANCEL,BYE,ACK,SUBSCRIBE,NOTIFY,MESSAGE,INFO,PUBLISH,REFER,UPDATE
User-Agent: Avaya one-X Deskphone
Supported: eventlist

<------------->
--- (12 headers 0 lines) ---
Sending to x.x.x.x:1032 (NAT)
Sending to x.x.x.x:1032 (NAT)

<--- Transmitting (NAT) to x.x.x.x:1032 --->
SIP/2.0 401 Unauthorized
Via: SIP/2.0/UDP 192.168.0.174;branch=z9hG4bK1_5a7d12149bcad5895ffc4_R2003;received=x.x.x.x;rport=1032
From: sip:2003@asterisk;tag=46c2abf4589053ec5895ffc0_F2003192.168.0.174
To: sip:2003@asterisk;tag=as5f37e30b
Call-ID: 1_5a7d0-b0875cb5895fbc0_R@192.168.0.174
CSeq: 1 REGISTER
Server: Asterisk PBX 13.1.0~dfsg-1.1ubuntu4
Allow: INVITE, ACK, CANCEL, OPTIONS, BYE, REFER, SUBSCRIBE, NOTIFY, INFO, PUBLISH, MESSAGE
Supported: replaces
WWW-Authenticate: Digest algorithm=MD5, realm="asterisk", nonce="2350c222"
Content-Length: 0