"Now there were no external links to these AWS subdomains but, being a domain registrar, Google was notified of the new DNS entries and went ahead and indexed l

"Now there were no external links to these AWS subdomains but, being a domain registrar, Google was notified of the new DNS entries and went ahead and indexed loads of pages" Domain registrars wouldn't be notified of new RR's inside a second-level domain - that would be pointless. I can't see any way they would ever index a URL that used a dns RR that was brand new - I'd hazard a guess that either the URL was used previously within the cloud and published somewhere, or it was set up as a CNAME in your own DNS, or your main webserver returned it as a response to a googlebot in some fashion at some point.