Mike from IG here. VPC was barely a thing when we got on AWS (2010) and at the time not the default. I would definitely have done VPC from day 1 in hindsight, though.
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.