I discovered the route of the problem when comparing the log files for packages that weren't detected as virus' by the AV with those that were. I discovered a difference when the bundle was being cached:
(Success) Caching bundle from: 'C:\Users*user*\AppData\Local\Temp{GUID}.be\Setup.exe' to: 'C:\ProgramData\Package Cache{GUID}\Setup.exe' Registering bundle dependency provider: {GUID}, version: 1.1.1.0
v
(Fail) Caching bundle from: 'C:\Users*user*\AppData\Local\Temp{GUID}.be\Setup.exe' to: 'C:\Users*user*\AppData\Local\Package Cache{GUID}\Setup.exe' Registering bundle dependency provider: {GUID}, version: 1.1.1.0
The reason for the difference is that the top MSI is a per machine installation whereas the bottom was per user.
In our specific case the MSI's shouldn't have been installed per user anyway but per machine and so changing them to be per machine installations fixed our issue.
Hopefully this might avoid others getting stuck in a similar situation but if anyone else has an answer that solves the "Per user" installation issue please share because that could become an issue at a later date.