I ended up figuring out that the router was "stuck" with the port open to a second device I was testing with only sporadically - which, if the game were still running on there would seem appropriate, but it wasn't.
This got me thinking though that the best thing to do is to give as many options to the player as I could - let them hardcode their own port if they are capable of doing it manually, or having the game pick a random port so it doesn't likely hit a "stuck" port. I also added a way to change the UPnP lease time in case that would be helpful.
But the results aren't as good as I hoped, and everything points to the routers involved. It's frustrating and I don't really have the time to read the specs closely enough to get a better understanding. The plan is to just start hosting the GameServers centrally, but until that can happen, I guess I'm just wondering what other kinds of workarounds people are doing.