I was able to do some more testing now with only WAN1 being No-NAT enabled (OS is 15.15):
1) The MX itself was failing over to cellular as expected. I could see the mobile providers' IP on the dashboard
2) On the local MX status page, the connection was also showing up as "Connected", the speed test had some good results
3) Strangely enough, the dashboard didn't provide any information about the cellular connection at that moment
4) No internal client was able to access the internet though
I guess it's really narrowing down to the No-NAT feature.