This post contains some bonus info for An illustrated guide to Amazon VPCs.
One reader added some fascinating insights:
Security groups were the original solution to the second problem (that everyone's servers were in the same network).
The address conflict problem transformed into another problem after VPCs. After everybody got default VPCs, companies went from conflicting with each other to conflicting with themselves. Now they have a bunch of instances with the same IPs, in different VPCs, that still need to talk to each other… a problem that needed double-sided NAT.
A big part of the first problem (IP address conflicts) was actually that AWS was about to run out of IP addresses to issue to customers.
Back then, every instance got a public address because there was no other way to ssh into your instance. Because public addresses are so expensive and limited, this was a scaling cliff for AWS, and passed on as an unnecessary cost to customers. VPCs let you use a single bastion with a public IP to access the rest of your hosts.