FYI, for my router/modem I can't match-make players on the same machine.

This means that your router doesn't support "hair-pin" NAT.

Your server can detect when two players are behind the same NAT (from the same source IP from the server's point of view,) and tell them to try a local match-up. Either have the client provide the local IP address it's on, or use UDP broadcast to find the other player locally.