A modern graphics card with up to date drivers can decode and play full 720p video without any real cpu processing power required.
My nVidia GTS240 (9800 equivalent, so the internet tells me) can fully decode 1080p video and leave my CPU running at 1-2% usage.
Do not use VLC as I do not think that it supports using the graphics card to decode HD video, it didn't last time I tried it. If you get the latest Divx package then it can enable Windows Media Player to handle .mkv files (which are quite common for HD video) and Windows Media Player can use DXVA to use the graphics card to decode the video. To be honest, I quite like the Windows Media Player, it's gotten a lot of polish since the XP and Vista days...
As a side note you can use GPU-Z to tell if your graphics card is doing the decoding, at least it does on my nVidia. In that program, on the "Sensors" tab, there is a "Video Engine Load" which gives an indication of how difficult the file is for the card. For 720p it seems to hang around the 7-15% area, for 1080p it goes up to 35-50% usage.
I would recommend you get a new graphics card, either a GT240 or better.
EDIT
As it was pointed out that the system was AGP (which I should've checked to be honest) there is a good likelihood that an up to date ATi might work as well as it seems that nVidia have completely abandoned AGP. I had a Radeon 3870 that worked quite well with 720p and "standard" 1080 content but failed with "high profile" 1080 video, newer cards and newer drivers would probably work better than what I experienced.
Maybe
GIGABYTE GV-R465D2-1GI Radeon HD 4650 1GB 128-bit GDDR2 AGP 8X HDCP Ready Video Card or
HIS IceQ H467QS1GHA Radeon HD 4670 1GB 128-bit DDR3 AGP 4X/8X HDCP Ready Video Card would work