Ahh, but this can never happen over the open internet. When the NATed sender sends mail to your NATed server, the server will not see the mail as coming from 192.168/16. It will see the sender's public, post-nat IP.
To put it more bluntly, the trusted_networks checks are only against the last (i.e. newest) Received: header IP addresses.
That's just false. Completely false. Trusted will work it's way back from the newest Recieved header and continue until it hits one with an untrusted host. There's no limit to the number of Received: headers it can consider trusted. It certainly can trust more than just the one.
The OP was suggesting that this could cause problems if both sides NATed and you trust 192.168/16. But that can't happen, because the NATed source will still appear as an untrusted IP, not 192.168./24, stoping the trust path cold.
So for your gateway to be receiving the SMTP connection, that Received: header would contain a real Internet IP address - or it was a connection from one of your own internally-NATted IP addresses - either way, the check should work.
Yes, that's fine, but SA does have trust issues if your mailserver itself is NATed and will resolve it's own "by xxx.example.com" name as a reserved IP.
I too was having difficulty with ALL_TRUSTED firing on incoming Internet mail a month ago, but it's all fixed now (I don't know if 3.0.1 fixed it? Can't remember)
Shouldn't have. There's been no change to the trust code, or ALL_TRUSTED in 3.0.1 vs 3.0.0. Perhaps you set trusted_networks?