Licensing Initialisation Error Windows XP

[#1]

I am running Windows XP.  I had an old copy of "Encarta" (remember that ?) installed on my laptop.  A couple of years ago, I bought a new copy of "Microsoft Autoroute Express" which I installed without problem.  Everything worked tickety-boo !
Then suddenly a year ago, whenever I tried to access "Encarta", up would come a message to say that "Autoroute Express" would not load.  I assumed that a registry entry had been corrupted and did nothing about it, as frankly I very seldom used "Encarta" any more.
"Autoroute Express" continued to work without any problem at all.  Until a few weeks ago, that is.  Suddenly I started to get a message "A licensing Initialisation Error has occurred: Error 0xC004D301".
I am at my wits end having tried everything on Google, none of which has helped.  The message is obviously common, however.
I have uninstalled "Autoroute Express" and "Encarta", run "cccleaner" to clean the registry and re-installed "Autoroute Express" several tiimes to absolutely no avail.  I still get the "A licensing Initialisation Error has occurred: Error 0xC004D301" message.  Checking "Add and Remove Programmes" in Control Panel indicates that "Autoroute Express" is not installed.  I have even tried to install it from the CD in Safe Mode but it would not let me.  There is no "Restore Point" early enough to which to restore either.
Does anyone have any suggestions what this might be about, and how I can fix it ?  I would be most grateful.
Thanks.

[#2]

This might help - http://www.wiki-errors.com/wiki-errors.php?wiki=0xC004D301

[#3]

MrT  Thanks for the suggestions but I had already tried that and it did not fix it unfortunately.

[#4]

You could try creating a second user account (with Administrator privileges) and install from that to see if you get a better result.  If that fails then it's time to back-up all your data and reset the computer to its factory state (or re-install Windows as appropriate).

[#5]

I tried that too but unfortunately to no avail.
I think that I have a clue.  I have discovered that "Encarta" is part of "MS Works Suite", which includes an old version of MS Autoroute Express although I had not installed it, as it was a much older version.  But my computer had installed a licence for Works Suite, which would have also been valid for the older version of Autoroute Express.  I discovered this because I noticed a file on the Works Suite set-up disk called Setup_AR.exe.  On the new version of Autoroute Express there is a file with the same name.  Now I imagine that there must be a clash between the two licences.
I have uninstalled all MS programmes, including both MS Office and MS Works Suite.  But unfortunately it took Outlook with it as well.  I re-installed the new MS Autoroute Express but came up with the same licensing error.  I shrugged my shoulders and started to re-install Outlook.  After the initial installation, I went to set up my profile and was astonished to discover that the profile and other settings were all still on the system.  That is bizarre because I had uninstalled everything, or so I thought.  But some residual data must still be lurking there, and not doubt buried in there somewhere is the old Works Suite licence number.
So does anyone know how else to completely uninstall root and branch all of MS Office and MS Works Suite ?  I have been using the Control Panel and the Add/Remove software facility.  Is there a deeper uninstall procedure ?  Where / how can I delete the licenses ?

[#6]

Have you tried this?
http://support.microsoft.com/kb/290301

[#7]

CX
Excellent idea.  I remember using Windows Installer Cleanup Utility (MSICUU2.EXE) when I had a problem with security updates for .net framework, and it sorted it all out for me.  I will definitiely give the new version a go.  But first I will uninstall everything again that I possibly can, run the CleanUp utility and try to re-install everything once more.  If that does not work, I will run it again with the new installation still loaded to see what happens.  I won't be able to do it now until tomorrow.
Fingers crossed !
Thanks for the idea.  I will let you know what happens.

[#8]

Same thing here, that's what led me to it (although I haven't tried that new utility). I remember back with Office XP having problems where Windows Installer got messed up, and you would get programs trying to configure Word when launching something totally unrelated like Acrobat Reader. Uninstalling, followed by the cleanup utility would usually fix it.

[#9]

CX
It's bizarre.  I ran the FixIt having uninstalled everything and re-loaded AutoRoute Express.  Same problem as before.
So I thought I would try to run the FixIt again.  But whatever I tried, I got the same messge to say tha this FixIt is no longer available !  It was available ten minutes earlier because I ran it !  So I tried it on my desktop computer where I had not run it before in case it had put something on the laptop to say that it has previously been run.  I got the same message again on the desktop where it had definitely not been run before.  It is quite weird.