I don't see the problem with VAT. Just keep rack of where your customers are and pay the VAT on those in Europe. Where does the payment processor come into it? If you owe VAT then pay it.
There are all kinds of rules on disclosure of VAT registration details on invoices, sequential numbering of VAT invoices (across an entire company) for audit purposes, etc. Any payment system that doesn't integrate with other company procedures to meet these basic statutory obligations can't be sufficient.
Sure it would be nice if they stored tax (multiple rates possible on one invoice!) and VAT numbers in a separate field, it would be even nicer if they validated the VAT numbers for you, or the buyers location, but it can all be done outside the payment processor.
As you say, technically invoices are supposed to record the VAT against each line item, because the rates can be different for different types of product/service.
Regarding the serialised invoice numbers, if you as the merchant are having to keep track of such things then you're still doing some of the tedious work so the value of outsourcing the billing process is lessened. I agree that it might be viable to record the extra information in a separate field for one-off transactions, if the billing service allows that kind of annotation on transactions and your systems can generate the appropriate number taking into account any other sales channels you're also using.
Even then, for subscription services that renew automatically, there would need to be some robust mechanism for the billing service to "claim" the next invoice number when they collect a scheduled payment. Perhaps some of these services could cope with this, but I have yet to see one personally whose documentation explains how to set it up using their APIs and callbacks. And if you get to the point where you have to handle scheduling regular subscription payments on your in-house system to account for this, again you're defeating the point of outsourcing the billing in the first place.
IME, it doesn't take long before you have to do so much in-house anyway that you might as well do the lot and save yourself a signficant overhead and the additional risk/dependency of involving another organisation in your billing process. This sort of processing is tedious but not rocket science, so if you can't just wrap everything up and shove it out to a specialist service, avoiding having to go near that sort of stuff in-house at all, I just don't see how the cost/benefit of these services is going to make them attractive to a business here in the UK. YMMV, of course.