Thanks for that advice. So I set about un-installing PC Companion and towards the end it "blue screened" on me and I couldn't re-boot my PC!
After using my Windows recovery disc I managed to get things running again and found that PC Companion was in some odd state, neither installed nor un-installed. I then re-installed it and found that the old problem was still present.
To cut a long story short, the "Re-starting PC Companion" issue turned out to be caused by my copy of "Soluto" running in the background. I had set PC Companion to a "delayed" start, rather than "paused", i.e. stopped. In other words it did not run at startup, but was delayed until some time after boot had finished. This is why it kept coming back! I then changed its Soluto setting to "paused" and it no longer runs unless I ask it to.
By the way I can recommend Soluto to anyone interested in analysing and optimising their startup processes. It's a free download from here: Soluto
Thanks again gregrocker