Your best bet is to figure out which registry keys and directory locations that the program needs access to, and give your users access to just those areas.
You can use a tool, like Process Monitor from Sysinternals for that. Simply log in as the user, start Process Monitor, and run the program and make note of the areas denying access.
I would probably use a Security Group in AD, and then give that Security Group access to those system locations. All you would have to do then is add users to that Security Group and they will be able to use that program on that system with their own credentials.