Multiple calls to PayPal were useless. They told me that when I applied for adaptive payments, they reviewed my entire account and decided to require that I always include CVVs. In over a year, I had almost no chargebacks so fraud shouldn't be the reason.
The next day I applied for Authorize.net and was accepted the following day. It's about about the same price as when I was with PayPal, but with none of the hassle.
In summary, if you want credit card based recurring subscriptions, PayPal is just as expensive, significantly more restrictive, has terribly designed APIs, a sandbox environment that doesn't work as often as it does, and is kind of like smoking next to a barrel of gun powder.