what do you do with 3 year old machines PCs running windows and are running slow? is it due to windows itself?

I am running into loads Dell XP machines that are around 3 years old that are running slow.  Not so much malware, but I feel, just an overall malaise or windows bloat.  But clients are not understanding / unwilling to accept that... that after this amount of time, the OS could / should be refreshed as a way to get the speed back on the machine?

I'll typically uninstall unwanted apps, remove temp files, clean and optimize the registry, defragment the hard drive, etc. and the machine still isn't working very good.  these are machines that are typically 3 GHz, with 512 MB or 1 gig of ram, lots of free space on the hard drive, etc.  overall, a nice machine, other than it's slow - which I  attribute to windows bloat (I thought I heard a cute phrase for that?).  even uninstalling apps, there's things left in the registry?  Thumb drives load drivers that stay around long after the thumb drive isn't being used?  every ative x or java applet that was loaded on a website stays in IE?  (see tools, programs, manage add-ons?).

but then do you backup all the data, reinstall the OS, apply all the patches (76+ when updating a new install of SP2 (yeah, I guess I should make a slip streamed disk with more updates?!), reinstall the apps and data, you hav a nicely running machine...  that is out of warrantee, the power supply, mobo, drives, etc are all 3 years old... the labor rate to refresh is a large % of a new machine (I, and I've seen others at the same amount, charge something like $300+ for that (depending on the number of apps).  Or that same $300+ will get the new machine setup, patched, same new apps installed, data and it'll be an even faster machine with a warrantee.

are there glaring holes in my thinnking?  What do you do in this situation / what do you recommend clients do?  am I off base saying that windows is the problem?