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