This whole discussion pretty much confuses me. Its so easy to clean this up.
I'm building and selling PC's for over 10 years now, special solutions for my customers. Gamers, business and servers.
Often I have clients with the same problems you describe and always some so called "pro" is giving another stupid advice.
Indeed in many cases the problem is that any of these just had some good experience with this component or with that component, disregarding the rest of your setup.
Oh well.
Step 1: Checking the OS
In many cases a real clean up of the OS is more efficient that buying directly new hardware.
Check for viruses, spy- and adware (
www.safer-networking.org is providing one of the best tools for spy- adware, called Spybot).
This tool provides also a nice advanced mode which allows to chose what really is started up at system start. In most cases 2/3 of all crap started during boot isn't needed and just eats up memory and cpu power, as well as increases boot time.
Things like Java, Nero, Realplayer, MSN, Adobe Reader, Google Desktop search etc etc etc.
I assume you already have a virus killer but if you need a free one try
www.avast.com or
www.free-av.com
Another tool called xp-antispy (works also for vista in many things) which can be found @
http://www.xp-antispy.org/index.php/lang-en/home can be used to easily disable some not needed background services like error report service, messaging service, windows balloon tips, uninstalling MSN or at least deactivate it if using Outlook express.
If you use a couple of messengers consider removing them all and try to replace them with some multimessenger like pidgin or trillian. I prefer pidgin (
www.pidgin.im) because its opensource and doesn't need much cpu power (but it is kinda spartan although it does everything needed).
Be sure to have a good defrag tool (I use
http://www.flashsystems.de/down/files/fdo.zip but its german, although easy to use) and defrag your drive or at least use the windows tool. Be sure to have all temporary files removed first- usually for XP in c:\windows\temp and c:\documents and settings\username\local settings\temp - you need to have "Show hidden files and folders" activated to see this path.
Once done check your System's drivers.
Most people forget to install the correct chipset drivers. Why? No clue, guess they assume it works already pretty well with Windows drivers. Of course it does work, but usually not with the maximum performance.
For almost all chipsets the driver can be found at the manufacturers page, like
www.intel.com,
www.amd.com,
www.nvidia.com,
www.viaarena.com etc.
Then check for the most recent graphics card drivers. The addresses for these drivers are almost the same than those above. I usually prefer the reference drivers instead of using the drivers from the card vendor. Usually less bugs and newer.
Don't forget your soundcard. Although usually not eating up that much performance it still can cause trouble if drivers are outdated. Many onboard chipsets are realtek. Those drivers can be found at
www.realtek.com
If you have trouble to identify your components go n grab siw (
http://www.gtopala.com/siw-download.html) it will reveal all your system hardware.
Why all this work?
Well, I saw that many people over all these yers, freaks and idiots who overclocked their system to gain maybe 10% more power out of their CPU or graphics card, risking a shorter lifetime of these or even blowing the system up in the attempt to do so, but wasting maybe 20-30% or more with some not correctly maintained system- yes it REALLY can eat up that much- or even more if some of the things I mentioned above is not done correctly.
I played for example Doom3 with an Athlon64-3000 and a Geforce FX5900XT @ 1024x768 and max details without problems. No overclocking, nothing special except a good cleaned up system.
Overclocking?
Overclocking can be a nice thing if anything else is done and if you are willing to take the risk to damage your hardware. For old hardware which is only worth some bucks it can really make a difference and if blowing a CPU for 10$- who cares. But if you don't have the money or you don't want to blow your new hardware its maybe not worth the risk.
As said, optimizing your system is often more efficient.
Another OS?
Although Linux is usually not the OS to play with it often seems to be faster than windows. So if the game(s) you want to play have a Linux port its maybe worth the try, but many games don't have a port so you have often no choice but to use Windows.
Step 2, the hardware:
1. Of course the first thing to check is the PSU (and I said CHECK not necessarily buy a new one)
Recent systems should have 500W or more. If some good quality PSU is used then even 430W is often ok (always depending on the built in components of course- for real high end systems maybe >= 750W is needed). Unfortunately some "mass product" PC's are having still only 300W which is then absolutely at limit then for the hardware it is running. Typical way to "earn" more money for those companies.
Why do you assume your PSU is to weak? If upgrading an old PC you need to check how much stuff you have and how much power it needs.
So some questions first:
What PSU do you have at the moment (Watts, Model)
How many drives do you have (CDROM/DVD/HDD/FDD/Anything else)?
What graphics card do you have?
All these things are necessary to know how much power the PSU needs. If you have only one DVD-RW and maybe one HDD it could be that your PSU is strong enough to feed some more powerful graphics card.
It maybe sound a bit harsh, but if not and its blowing up- usually the hardware is not damaged. No guarantee for that of course, but that's the way it is in most cases.
2. A new VGA (graphics) card?
To decide this its a good idea to check whats the recommended minimum requirements for the game(s) you want to play.
I read the comments above about that- wondering nobody noticed that these recommendations are (often) meant to be MINIMUM requirements.
A new graphics card depends also on your mainboard and CPU.
An example:
If the minimum requirements are maybe a Geforce 8XXX but your system is AGP only I would think twice about to buy a new card because if some day the mainboard blows and and you must buy a new one you definitely need PCI-Express then- if there even is still some AGP Card with the required specs. Also a Geforce 8XXX is of little use if you only have a CPU like P4-2.4 or so.
And as mentioned already a new PSU is maybe required also, so is it still worth it?
In short if you want to update an old system, it should be updated maybe with some old graphics card which can be found pretty cheap at E-Bay or so. Don't waste a lot of money in an old System, better to save your money then and buy a complete new set (PSU/Mainboard/CPU/Memory/Graphics Card) when you can afford it.
Onboard chipsets however are usually pretty slow, often cause problems with OpenGL and use the way slower system memory (compared against the memory used on recent graphics cards).
So buying a new card is often a good choice because you will have more system memory then and its generally faster.
Nowadays a card should have not less than 256MB, but memory is not everything. The biggest memory is of no use if the card itself is slow. Checking the web for performance tests and to compare the different chips maybe at least at the manufacturers page is always a good idea.
Ati or NVidia or...?
A question which can't be really answered. I prefer Nvidia because usually the drivers cause not that much trouble as ATI's. On the other hand ATI offers often cards which have more power for the same price.
SingleCore, DualCore, QuadCore...
Many applications don't support more than one core so the performance gain is still very poor. Check if the application or game really can benefit from such a technology. If not this advice is a bad one.
However, if you consider to buy a new CPU anyway (because of the minmum requirements for example), then those CPU's with multiple Cores are often not more expensive than those with fewer or single Core technology. Then buy some "multicore" of course, newer applications or updates will benefit more and more from it.
But check if your mainboard is really supporting these. Sometimes a bios update can help to run the new CPU's but not every mainboard supports every CPU even if the chipset should be able to handle it. Check the page and/or the forums of your mainboard manufacturer.
If your mainboard does not support it and/or it still uses DDRAM and/or is still having AGP I'd consider anyway to save your money until you can afford a complete new set.
---
I just wrote that within a few minutes and I hope I considered everything important for the moment. Will have a look later again if I misspelled something etc.

Consider this just as a short advice.
If you have some other hardware as my examples above, just tell, for most things I know where to find in the web.
In the end If you really need to buy new hardware its often good to check in the web for tests and reviews. Pages like tomshardware are a good choice. And try to ask in the forums but maybe more like:
"I have this PSU, this Mainboard and this Graphics Card, what do you suggest? "
And compare the different opinions and answers with what you have learned already.