I don't believe in "normal windows build-up" (it's almost always a virus or a badly-written program/uninstaller that wrecks windows,) but I'd agree that running memtest and testdisk is a great idea. If your hardware is fine and your data is backed-up, a wipe can do wonders.

Having a full hard disk causes Windows problems, for sure. It really doesn't like it.

There's some cases where a particular edition of XP only works with keys for that edition, but usually you're good with any disc.