My reading of the council response is that VAT registration is not, in itself, relevant to them but is being used as a proxy for evidence that the company named on the invoice actually exists a genuine company in the towing/recovery business. So the combination of no VAT registration and no street address for the company has raised their suspicions that it may not be a genuine recovery company. If they had the VAT number they would be able to check if it is genuine -
https://www.gov.uk/check-uk-vat-number - and a street address they could check in other sources they have access to. An email address means nothing and it can't be validated that it is the email address of the towing company. Anyone can set up an email address.
Why you would go the bother of hiring a fake recovery company just to avoid their PCN is a mystery known only to the council.
So if you are going to take it further is there other information of the company's existence you could use? Is it registered at Companies House? Does it have a website? Evidence of advertising?
I assume as there is no VAT number no VAT has been included on the invoice?