Este não é o melhor sítio para fazeres perguntas sobre questões legais. O melhor sítio é o escritório de um advogado.
Os servidores de VPN encontram-se em datacenters. Desconheço, e parece muito improvável, que tenha de pedir qualquer tipo de autorização aos ISPs dos mesmos, até porque, essa infromação não me poderia ser fornecida.
Isto é uma não-resposta que me leva a tirar algumas conclusões precipitadas relativamente à vossa experiência, pelo que vou partir do princípio que o vosso objectivo é "idealista" e não "malicioso".
Tem uma coisa em mente: podes procurar dar as voltas que quiseres para (não) justificar o que (não) quiseres justificar. Algum contrato pode não ter alguma cláusula específica sobre esse assunto. Podes nunca ter perguntado. Podem nunca te ter dito. É completamente irrelevante.
Certamente o contrato (ou os termos e condições, ou a acceptable use policy, ou qualquer um dos inúmeros documentos que tiveste de aceitar) diz que o que fizeres com o servidor é da tua responsabilidade. O que passa no servidor é da tua responsabilidade. O tráfego gerado pelo servidor é da tua responsabilidade.
Isto significa que, se e quando alguém bater à porta do ISP a pedir explicações sobre o IP do teu servidor, é para ti que eles vão encaminhar. Idealmente, tu também terás a informação certa para os encaminhar para outro lado.
Não é por acaso que existem relatos de no-log VPNs terem sido apanhadas a guardar logs, e em alguns casos fornecido esses logs às autoridades. Uma coisa é o marketing, outra coisa é a responsabilidade a que elas
sabem que estão sujeitas. A honestidade não é um requisito em marketing (excepto quando são apanhados).
No-log VPNs atraem todo o tipo de clientela que é garantido que vai procurar usufruir dessa promessa
às tuas custas. E a não ser que o teu público-alvo sejam jornalistas ou activistas em regimes opressivos - que de qualquer modo são espertos o suficiente para evitar serviços menos conhecidos (nem os mais conhecidos - existe algum equilíbrio naquilo que usam) - não me parece que vás ficar em boa companhia. Se forem, então consegues ficar numa situação pior, porque passas a estar no radar desses regimes.
Para teres uma ideia do que te espera, recomendo que vejas as dicas que são dadas aos exit nodes do Tor, que me parecem ser análogos à tua situação:
https://blog.torproject.org/tips-running-exit-node
Dito isto: não faço ideia o que é que alguma lei diz em relação aos logs das VPNs (e nota que falas em "regras europeias" mas é relevante distinguir o país onde estás, ou de onde és cidadão, mais a sede do ISP dos teus servidores, o país onde os servidores efectivamente estão, o país que o(s) contrato(s) que assinaste diz(em) que interessa, e porventura o país de onde o tráfego desses servidores sai para a Internet se não for directo - as leis de cada um são relevantes). No entanto, qualquer que seja o caminho que pretendas seguir, é muito provável que o venhas a ter de defender em tribunal, e responderes com "não sei quem foi" é meio caminho andado para seres o suspeito principal de uma investigação.
Portanto parece-me que guardar registos de acessos e netflows é um no-brainer. É a vossa única protecção - e mesmo assim podem ter de comprovar a sua integridade.
Finalmente, posso acrescentar uma perspectiva pessoal: conheço uma pessoa que teve de explicar à PJ porque é que o IP dela apareceu associado a uma rede de pornografia infantil. Aparentemente, ela era utilizadora de um serviço de VPN peer-to-peer (acho que browser-based), cujo modelo era o tráfego dela sair pelo computador de outra pessoa, e o tráfego de um terceiro sair pelo computador dela, sendo que quem pagasse pelo serviço não era obrigado a ser um exit node mas ela usava a versão gratuita. Isto aconteceu há meia década e ainda não está resolvido.
Quanto ao IVA, se vocês estão para abrir um serviço, têm de ter um contabilista, que é também a pessoa indicada para vos responder. De qualquer modo, o IVA é obrigatoriamente cobrado a qualquer cliente dentro da UE. A taxa varia com o país
do cliente. Não cobrar IVA (aliás, não pagar o IVA devido, nem que tenhas de o tirar das receitas) é uma forma de fraude fiscal.