In our setup we have a Network Load Balancer (NLB) that forwards traffic to the Application Load Balancer (ALB). In order for the ECS Service (private Subnet which contains an inbound rule for NAT Gateway) to perform the Health Check it needed to call an external endpoint (out), then get a response (in).

The solve was to add an inbound entry to the NLB > Security Group for HTTPS port on the NAT Gateway IP.