Remote Desktop only connects on same network (not using local IP)

Question

What could explain remote desktop connection (RDC) failure depending on the client network? I have a RDC that uses my public IP, but the connection only works when the client is on the same network as the host. I would think that the client network would be irrelevant when using the public IP.

• Remote desktop connections are enabled on the host.
• The host firewall is letting RD through.
• Port forwarding is set up on the router.
• The whatsmyip.org port scanner shows that the RD port is open.
• I set up the connection on two different Android devices.*
• The connection uses the public IP (or a domain name set up through DDNS).

While a client device is on the local network, I can start the connection with no trouble. Then I disconnect and turn off the WiFi on the client so that it is using the wireless carrier network, and the connection fails with error 0x3000062 ("Remote Desktop Gateway is temporarily unavailable"). I have also tried this with the client on networks at shops around town and from work and always get the same error.

I saw in this question that the person said their ISP was blocking the port. The ISP claims that they are not blocking any ports. My router is behind a modem provided by the ISP, but they claim that the modem is not blocking anything.

*I do not have any other device to test with; I am trying to use the RDC to do work on an Android tablet while my laptop is being repaired.