Adding a single character to the length (from five to six) would probably have been enough to keep them off the radar by making it dramatically harder to bruteforce. I would not be surprised if this single extra character would have completely diverted the attack, since the miss rate would be so high, it would trigger S3's DoS protection.

Doubling the characters to 10 would pretty much completely solve the problem. It would take many, many years to find a single image. Far below the threshold where Amazon S3 would ban you.