I had this same issue with every deployment technology I have tried to use. Visio always repairs, but I found a workaround
Search the registry for "C:\Program Files (x86)\Microsoft Office\Office16\VISIO.EXE" and replace it with "C:\Program Files (x86)\Microsoft Office\Office16\VISIO.EXE /noreg"
Next replace the icon in the Start Menu folder with a manually created icon adding the /noreg switch at the end of the command-line
