¿Están ejecutando todos los usuarios el mismo ejecutable directamente desde el servidor?
Si eso es así es una muy mala práctica que te puede acarrear problemas.
Como bien dices deberías hacer un instalable para que cada usuario se lo instale localmente y se actualice al ejecutar la aplicación si detecta nueva versión.
Por suerte esto es muy fácil con Visual Studio y ClickOnce.
Tan solo tienes que pulsar botón derecho sobre tu proyecto, pinchar en "Publicar" y seguir los pasos.
Básicamente se te pedirá que indiques el destino del instalable (yo escogería "Alojar en un CD-ROM o DVD-ROM" para que te genere los ficheros en local y los distribuyas como quieras) y donde debe buscar actualizaciones (en tu caso yo los dejaría en una carpeta compartida del servidor donde lo están ejecutando actualmente).
Al hacer esto te abrirá una carpeta donde verás una serie de ficheros y carpetas con un ejecutable "setup".
Al hacer click en setup se instalará en el ordenador actual.
ClickOnce es mucho más complejo ya que permite indicar dependencias, intervalos de actualización, idioma, etc... pero para eso te dejo mejor el enlace oficial de la MSDN:
https://msdn.microsoft.com/es-es/library/748fh114.aspx
Saludos y bienvenido a Todoexpertos 😌