OK I try to explain the problem better:
If someone from outside the EU places an order (tax free), and the delivery address is also outside the EU (tax free), we do not have to charge VAT.
But if someone from outside the EU places an order (tax free), and enters a delivery address inside the EU (not tax free), we have to charge VAT.
I've set the "Type of of address used for tax" to billing.
We have tried it with "Type of of address used for tax" set to delivery, but then we had an issue when an european company with a valid VAT-Id orders (tax free), and enters a private person as delivery address (not tax free).