>> Scan the entire internet for domains pointing to s3-website, and check AWS API to see if it's available?
What I wonder is how do you scan all the DNS records with their subdomains? Unlike IPv4 address space, which is very decidedly finite and not-too-big, the space of all the subdomains is basically infinite.
Other than using AXFR (zone-transfer DNS request) which is usually restricted, you are searching an unbounded space.
I guess you don't need an AWS API calls since hitting a non-existing bucket with HTTP will let you know: http://something.that.does.not.exist.s3-website-eu-west-1.am...
IOW, how would you write such a bot? :D