Hi Mark,
could you please check the uninstall .log on these machines? Do you see the "Lindersoft\WebUpdate\AppPaths" registry keys and entries in the log?
If this is not the case: is your initial installer "requireAdministrator" manifested?
Friedrich