Upgrade a Windows Service without Uninstalling

I’ve done this with WiX, which generates .MSI files using the ServiceInstall & SeviceControl commands:

<Component Id='c_WSService' Guid='*'>
    <File Id='f_WSService' Name="WSService.exe" Vital="yes" Source="..\wssvr\release\wsservice.exe" KeyPath="yes" />
    <ServiceInstall Id='WSService.exe' Name="WSService" DisplayName="[product name]" Type="ownProcess"
                    Interactive="no" Start="auto" Vital="yes" ErrorControl="normal"
                    Description='Provides local and remote access to [product name] search facilities.' />
    <ServiceControl Id='WSService.exe' Name="WSService" Start="install" Stop='both' Remove="uninstall" Wait="yes" />
</Component>

This stops the service, installs the new version and re-starts the service.