紐づくEC2インスタンスを停止したElasticIPアドレスは、NATゲートウェイに紐づいていれば課金されませんか？

NAT Gatewayに紐づいていれば課金対象にならないと思います。
注意点として2024 年 2 月 1 日からはリソースに紐づいていても課金対象となります。
https://docs.aws.amazon.com/ja_jp/AWSEC2/latest/UserGuide/elastic-ip-addresses-eip.html#eip-pricing

Elastic IP アドレスを効率的に使用するため、Elastic IP アドレスが実行中のインスタンスに関連付けられていない場合や、停止しているインスタンスやアタッチされていないネットワークインターフェイスに関連付けられている場合は、時間毎に小額の料金が請求されます。インスタンスを実行しているときは、インスタンスに関連付けられた 1 つの Elastic IP アドレスに対して料金は発生しませんが、インスタンスに関連付けられた追加の Elastic IP アドレスがある場合、その追加分に対しては料金が発生します。詳細については、Amazon EC2 オンデマンド料金ページの「Elastic IP アドレス」を参照してください。

2024 年 2 月 1 日から、実行中のインスタンスに関連付けられているものも含め、すべての Elastic IP アドレスに対して課金されます。詳細については、「Amazon VPC の料金」ページの「パブリック IPv4 アドレス」タブを参照してください。