They could provide salted hash verification: send some salt, get a list of files with SHA1(salt | filedata) via email some hours later (so they can do the verification as a low priority job).

The salt is used to prevent amazon from just keeping the hashes around to report that all is well.

To avoid abuse, restrict the number of free verification requests per month.