I think the CC providers charge merchants for these. Do you know that to be incorrect? If I'm correct this means that it now costs email providers cents per account per month, which just took an expensive turn for the worse.
If it doesn't work that way I bet Visa amends their merchant agreement to start charging -- they aren't in the business of doing millions of identity verifications per month for free.
Oh, you definitely pay for the privilege of submitting Auth requests. You have to have a merchant account with the card issuer. The systems I've worked with went through a third-party gateway system which connects out to all the different card issuers. It's definitely not cheap to set up. I'm not sure if there's a per-request charge or not. I wouldn't be surprised either way.