Alright, I hate to massively bump this like I am but after numerous months I finally found the solution to the problem. Perhaps someone might find this information useful.
Unfortunately this is after I dumped the whole Legacy Gaming PC idea and made it into a sort of HTPC.

The problem was I was accidentally underclocking the CPU. The value for CPU clock was not in percent like I thought and so I had it set to 100 where normal clock is actually 200. That said, I'm sure the Matrox or other AGP cards would have worked well with this motherboard. Unfortunately it's too late to find out now, unless I decide to make another PC.

Problem solved, finally. I knew it was a dumb user error when it started happening on XP as well.