Despite "The NAT settings of the SPA112 are exactly the same as the SPA504G" I'm almost sure it's NAT related issue.
I assume the NAT changes source port of RTP (audio) stream if the source port number used by SPA112 is considered used - but it doesn't patch SIP packets accordingly. In such case the RTP stream is not recognized by peer.
If source port is not busy, then it's passed thru NAT unchanged, so everything works.
To verify such hypothesis you need to packet dump (SIP as well as RTP) captured *after* the NAT. Ask your local network administrator for help if necessary.