Running applications in background

Hi,
I’ve got an executable that I want to run automatically on a users machine.
The machine is runnig xp.
I want the application to run on startup regardless of who is logged on. I have tried putting it in the startup folder within the all usersdirectory but it doesn’t seeem to run automatically for all users.
I also want it to shut down automatically when a user shuts the machine down.
Does anyone know how I might be able to do this?
Can I run it as a service?

Phil