I id have some problems with algo behind a NAT. Though my usecase is a bit different, more of a road warrior, as I wanted to be able to access a server in one property (behind NAT) from my home PC (also NAT).
I suppose I just need port forwarding.
I was in a similar situation. Port forwarding worked perfectly. In my case the server I was trying to access was behind an ISP (Comcast) managed NAT so I had to go through them to open the port. Much to my surprise they were extremely helpful and understanding of the request.
Was this residential or business? I didn't know there were Comcast managed NATs beyond their internal network.