XP SP2 Automatic Service Problem

I've got a strange problem. I work at a local library and we have a
proprietary software system for logging people onto public terminals
with their library card. The launch of the client depends on two
things, first, a shortcut in the startup folder to a exe file that
works fine. The second is a XP service. The problem we are having is
that the service, though set to automatic, does not start
automatically, if you go into Services and start it manually, it comes
up and runs fine. There are no messages in the event logs.

Some history. We got a few new PC's and out of the box I installed
SP2 on them. Later we installed the client. In troubleshooting a
different problem we uninstalled SP2 on 1 of the machines, this is
what caused the problem. On the machine that had SP2 installed before
the client, that works fine. Also, on a different machine, the client
was installed on top of XPSP1a. That machine was upgraded to SP2 and
has the exact same problem as the other. Now I have uninstalled and
reinstalled SP2. I have thoroughly uninstalled the client removing
every file and registry entry and reinstalling it. I have tried using
different builds of the client. All with no change.

The interesting thing with this problem is that the client IS in fact
SP2 complaint. It is just not SP2 install or uninstall compliant.
Something happens in the install/uninstall routine that screws up the
service launch. I have searched for utilities that examine the inner
workings of XP's service load order and found nothing. I should also
note that these are XPPRO machines, as I did find some service load
information for XPHOME that was not the same for PRO.

Any information about utilities or anything to examine or hopefully
modify the service loading procedure would be greatly appreciated. In
fact any suggestions or theories would also be greatly appreciated.

Cheers.

Joseph