While we haven't seen this issue with Visio, we did run into the issue with the entire Office Suite when upgrading from 2013 to 2016. We resolved the issue by adding the NoReReg option in HKCU hive of the registry (had to be done with profile management tool, we are not using UEM/DEM).
reg add HKCU\Software\Microsoft\Office\16.0\Word\Options /v NoReReg /t REG_DWORD /d 1
reg add HKCU\Software\Microsoft\Office\16.0\Excel\Options /v NoReReg /t REG_DWORD /d 1
reg add HKCU\Software\Microsoft\Office\16.0\Access\Options /v NoReReg /t REG_DWORD /d 1
reg add HKCU\Software\Microsoft\Office\16.0\Powerpoint\Options /v NoReReg /t REG_DWORD /d 1
reg add HKCU\Software\Microsoft\Office\16.0\Outlook\Options /v NoReReg /t REG_DWORD /d 1
The path is the same for Visio, though I can't confirm if it will resolve what you are
reg add HKCU\Software\Microsoft\Office\16.0\Visio\Options /v NoReReg /t REG_DWORD /d
