If we are able to modify the DHCP server to do something sensible, why not modify default router settings to issue /16 addresses instead of /24? Or even 10/8? There's plenty of RFC1918 space to not run out.
NAT state tables won't have to stretch that far as they can time out unused connections just like they do already.
Would there be any unintended side-effects with doing this?
If you don't like the NAT, go ahead and issue IPv6 :-)