Well,
that could be most likely the problem then.
Because the check also works so, that the country code of the shopper address entered must match the code in VAT.
That means, that if you use VAT ID starting with 'DE", the shoppers country must be "Germany"; (and the 2 letter code in VM table of countries must be DE -- which is default).
If the country does not make it though on your website from some reason, then the check will fail -> and thus VAT will be charged.
To solve this, you should check, what is the problem with country in the order form.