It doesnt have to get ulgy , its a fairly easy process , it just involves lots of parameters.
First you have the uninstall.exe right,
Next you create a login script through group policy that affects those pc's ,
Third make the policy get applied when the user logs onto the pc, upon boot, make the login script run from the group policy and make the script call on the executable.
I believe you can even put the executable within group policy wthout having to use a login script,
If you do it through group poicy , you can modify the grou policy that you network already use to call on the exe, and the exe can be placed in the sysvol directory which will infact replicate to all the domain controllers,
When the user log at their site then they will run the exe from the domain controller where they are currently located without blogging ou the network from one location.