It's been one of the best architecture decisions I've ever made. At this point we only use one public IP address. (If direct access to a machine is needed then you can connect via VPN running on the one bastion host with the public IP address, and this gives your machine access to the local IP addresses of instances running inside the VPC.)
All the machines in our cluster are protected inside local VPC address space, with the access by the external world being ELB to expose public service endpoints like the API and website. I can't think of any good reason why you wouldn't be using VPC in the first place. Having public IP addresses for private machines sounds like a recipe for disaster if you ever accidentally miss a port in your security rules.
I think you guys did an exceptional job to tackling a really difficult problem (I've been in the same position, migrating EC2 to Datacenters) and we determined that EC2 -> VPC -> Datacenters is really the only way, and Neti solves it surprisingly well.
Going forward, hope that acquired companies opened their AWS accounts late enough that Amazon forced them to use VPC.
In any case, the migration is daunting even at our size, although our devops team size is 1. I do wish they had VPC when we started.