> Not sure how you could do that efficiently...

You could probably do that quite efficiently with Passive DNS data. There are a bunch of providers (e.g. FarSight, RiskIQ, many others) that collect and aggregate DNS request data and make it searchable over time.

RDNS is probably not going to be helpful. I'm not aware of any cloud provider setting a PTR record by default, and I think most won't allow you to do that at all.