Every couple of years I'll reformat.
I only install lightweight apps that I really need, if I ever do uninstall something I use regclean, ccleaner, and autoruns to make sure anything uninstalled is really off my system.
Keeping windows xp very clean like this I've never noticed a slowdown the last couple of years.
I do like to do a full uninstall and re-install of firefox from time to time, because I have found old firefox installs seem to slow down over time.