In answer to your first point ... if you haven't heard of them ... don't use them ...
It's not just that they are rubbish (which often they are!) it's the other payload they could conceal such as keyloggers and bots that are the real concern.
Stand in your local newsagent or supermarket ... flick through a couple of PC mags ... and follow their advice ... Mainstream may be boring ... but it's become mainstream 'cause it works and won't empty your bank account..
If you've just had a recent re-build ... you shouldn't need a restore ....
My test rig is used daily ... I load/unload new software and Utils often daily
even antivirus s/w... as well as live viruses to see how the antiV copes
and I have used the same build for 6 months now ... without problems.
Most programmes will leave their registry entries.
Look in HKCU\software & HKLM\software
(you'll see entries for almost every prog you've ever loaded - and unloaded!).
The point is that the registry is extremely efficient "cleaners" etc rarely if ever make any measurable difference to the running speed.
If you send the machine to be rebuilt - next time get the guy to create a recovery image ...
or try
http://www.runtime.org/dixml.htm
and make your own BEFORE you connect to the net.
A fully configured system restore takes about 20 mins ...
so you could re-build daily if necessary
Your second Q.
1 - is it just your sites ... or all sites?
if just yours ... possibly you are using absolute refs
(publisher isn't really suited to websites)
look at the page code (notepad is good enough)
the links should look like this
Home
or this
13:54 Mon 14th May 2007