No - we never did get this resolved.
We engaged the contractor's parent company to see if they could enable NAT traversal, or at least look into it - but beyond saying that they would look into it, were not able to get any attention on the topic. The immediate project need has diminished - as the initial scope was completed - but I envision this coming back up again soon. If I knew exactly what they were doing on their end I would try to reproduce the scenario, but as it stands we're at a dead-end until it the need comes back up, or until we run into a similar issue with a different client.
If you make any progress on this in the iterim - I would love to hear about it - please post and/or PM me. I'll of course do the same if/when it becomes an issue again for us.
Thanks!