Have you considered some sort of "crowdsourcing" / voluntary botnet type approach?
The ArchiveTeam[1] have a simple VM image that anyone can use to schedule and coordinate large site archival jobs that might already address some of teh issues.
Might be tricky to find people willing to provide resources, but with even a smallish group it might work out. May need to consider abuse and run multiple queries and compare results, which might add to the overall request cost.