We've debated this at length with HMRC and our accountants. Because the service is 'used and enjoyed' within the UK for a UK based service (i.e. the servers are in the UK), we have to charge it.
We don't charge VAT to UK/EU individuals using our US based services.
Look at GoDaddy, 1&1, etc... the really big guys that the EU have come after for incorrectly charging it before and are now charging it.