We are currently researching a similar problem with Vista where the SplendidCRM plug-in does not appear even though it is registered properly.  The problem on Vista is that Outlook needs elevated access rights to enable the plug-in.  We are hoping that Microsoft can help us resolve this issue, but in the mean time, the solution on Vista is to run Outlook as an administrator.  This is easily done by right-clicking the icon and selecting "Run as Administrator".

I mention this Vista problem because it may be the same problem that your folks are experiencing on XP.  Please have your XP folks try the "Run as Administrator" trick.