Elastic IP for NAT gateways

An Elastic IP is used because it allows you to detach the IP address from the NAT Gateway and then reuse it again for something else that is public-facing - even another NAT Gateway. This is useful because many organisations use your IP address as a (very blunt!) security mechanism to allow access to their applications; so having the ability to migrate the Elastic IP from one NAT Gateway to another is very useful.

If we were to use a Public IP for NAT Gateway that IP address would go back into the larger pool of available IP addresses when a NAT Gateway is decommissioned. Then you have no opportunity to reuse it which might cause you pain. As it is, if you don't want to reuse an Elastic IP you can release it anyway.