Frustration: How to let restricted users run a program that accesss registr

Hi

we have 1 x windows server 2003
and 10x winxp pro machines in a domain .

Each user on each machine needs to run a progam called CLIENT.exe and client needs to edit a couple of registry keys each time it runs.

problem is that restricted users cant run this program, because of the registry editing issue.

Adding the program as allowed under software restriction policies for the domain did NOT help. We must not use RUNAS commmand, and cannot make the users admins.

I have spent 17 straight hours trying to figure this out and am close to pulling out all my hair… Will highly appreciate your help!!!
thanks
Effahid