I wouldn't consider it an answer (just a workaround), but I've had a lot of luck with Hamachi.
Like you, it seems, I was able to get the game to report NAT level (moderate) on a single attempt, and my guest connected normally. After it later crashed, the game only reported me as "TBD" and my guest wasn't able to rejoin.
After firing up Hamachi, we connected right away.