Desde que o desinstalador do instalador e esteja bem escrito, então não deverá haver nenhum problema.
A reinicialização é necessária porque o instalador precisa substituir um arquivo atualmente em uso. Isso acontecerá quando o sistema for reinicializado em seguida. Você obteria o mesmo quando o aplicativo / serviço usando o arquivo foi reiniciado.
O desinstalador deve verificar se nenhum outro aplicativo requer um arquivo antes de removê-lo do sistema. Eu não tenho 100% de certeza dos detalhes, mas acho que o Windows (digamos) mantém um registro de quais aplicativos usam quais dlls. Quando um desinstalador tenta excluir a dll, ele diminui a contagem de uso e só é realmente excluído se a contagem chegar a zero.
Por segurança, se você está instalando uma nova versão de um programa, provavelmente é melhor desinstalar a versão antiga antes de instalar a nova versão.