Three things are strange:
Codecs: Confirm that the codec setting for the Trunk has ulaw as the top choice (and preferably no others).
4070 INVITE sip:[email protected]:5060 SIP/2.0
I assume that this is an on-site PBX and 192.168.0.19 is its LAN address. This seems to indicate that the router/firewall has a SIP ALG enabled (if in Asterisk SIP Settings, External Address and Local Networks are correctly set, VoIP.ms should have no way of knowing the private address). Try turning off SIP ALG.
Asterisk did not even execute the Inbound Route logic, yet you claim that if you change the Inbound Route to point to an extension other than the HT802, the call succeeds?