If you add a elevated startup item through the normal method or through Run in the registry, then the user would get a UAC prompt at startup for that startup item. If it was a standard user, then they will not be able to allow it run unless they had the administrator's password.
A task would be the best method to allow the elevated start item to run on all user accounts at startup. However, I have no idea how to do it remotely though.
