Allow anything that passes basic validity checks, then send a nice email a few days later asking for updated payment info. This is easiest if you're a subscription service as you'll want to have a process for recovering customers with expired CCs anyway. This is assuming you're in the usual case where the paywall is to stop free riders and not to reduce your costs.
Depending on the specific nature of the content (news content comes to mind) you could even just grant access for 24 hours and revoke it if fraud detection fails. This solution wouldn't work well for all types of content where the feature could be abused to harvest static content.
Do paywalls face as much fraud? My understanding is that industries that provide digital goods or services see a much lower rate of fraud because there's little resale value involved (and the cost of stolen/returned goods is much lower).
It sounds like the biggest problem that OP is talking about is people using his service to validate credit card numbers. They don't particularly care about the candy, they just want to know if a number has been cancelled yet.
He's not concerned about fraud where he is out goods, he's concerned about fraud where he's being used as a card verification tool. Checking the validity of credit cards is expensive and hard for carders; They need to do so fast and in bulk, but without setting off the fraud detection on the other side and killing the card.