There's actually a kind of stateless NAT where each host gets a source port range. I believe it was involved in one of the IPv6 transition ideas.