Thanks people.

Actually I have tried running as a service (including one interacting with the desktop), I have tried running it under different user ids, the paths are full paths, there are no mapped/network drives in it.

Most likely it is something hardcoded into the exe itself which requires a user to be logged into NT, so I was going to attempt to fake a login and then run the exe.

Could be I may just have to re-write the exe myself...that would suck.