How are you referencing the executable?
If you've got a full path variable: myExe = r'c:\folder\doSomething.exe' try swapping it to something like:
myFolder = r'c:\folder' #this is the same item thats registered with the datastore
myExe = os.path.join(myFolder, 'doSomething.exe')
Or maybe you have it that way, and you want to switch it to the full path. I'm not in a position to test this right now, but I know one (actually though, both ways) should work.
What version of Server?