Setting %PATH% for a service?

The offending directory is specified either in the system-wide PATH environment variable, or in the Local System user's personal environment variables.

The Local System user's personal environment variables are specified at HKEY_USERS\.DEFAULT\Environment. The machine-wide environment variables are specified at HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Environment. The former isn't really easily accessible from anywhere except the registry, but the latter is accessible from the Environment Variables dialog on the Advanced tab of the System Properties.