The MX does not send 404's - something else is doing that. I'm guessing it was broken before, and is still broken, and is not related to your core issue.
Traffic shapping rules will have no impact on all inbound calls breaking. This is an unrelated issue.
If only inbound calls are not working then it will be something to do with the processing of NAT traffic.
Do the phones ring, you answer, and they fail to get voice working? Or do the phones not ring at all?
For all the phones we do we use SIP/TLS. Being TLS the entire call setup is encrypted. Consequently ALG's can not see the traffic or interfere with it. Also it allows the CPE to track the session because it sits on top of TCP, rather than UDP.
If you can't use SIP/TLS then the second option I recommend you try is SIP/TCP.