The specific issue with Recurly that we had is that they silently changed their platform to perform VIES validation on all VAT numbers. While this makes sense for transactions with entities from outside of the merchant's country, validating VAT numbers for German-to-German or Spanish-to-Spanish transactions is silly. Not only do such transactions always get charged VAT, but it's possible that a given string is a valid VAT number and yet is not present in VIES. Since you will pay (and therefore charge the customer) VAT for same-country transactions anyway, you don't care if the number that the customer provided is valid according to VIES.
This change has cost us a little wave of support tickets and an ugly workaround, in preparation for moving off Recurly.
I firmly believe that a company that gets online recurring payments right in Europe will become a money-printing machine in no time.
1. Recurly is right to add VIES validation for out of country transactions.
2. They shall not implement this feature for in country transactions.
German customers who buy in a german webshop have to pay VAT and then claim it back later in their tax return, because the german tax authorities don't allow that exemption beforehand.