One possible answer: pay them for their trouble until you provide value to them, e.g. by paying some fraction of a cent for each (document) request.

Cool, you wanna solve micropayments now or wait until we've got cold fusion rolling first...?

You wouldn't have to make them micropayments, you can pay out once some threshold is reached.

Of course, it would incentivize the sites to make you want to crawl them more, but that might be a good thing. There would be pressure on you to focus on quality over quantity, which would probably be a good thing for your product.

>You wouldn't have to make them micropayments, you can pay out once some threshold is reached.

Believe it or not, this is a potential solution for micropayments that has been explored.

I could even pay a fixed amount to my ISP every month for a fixed amount of data transfer.