I know it's a bit late to reply but here goes anyway..
It's amazing how well these K6-III+ chips have stood the test of time - I too, used to own one (450) until finances forced me to sell it on eBay.
I also bought it to overclock, on a 112MHz bus:
K6-III 450 @ 560MHz
112MHz FSB (74MHz AGP/37.5MHz PCI)
1x 128MB PC133 SDRAM
Soltek MB with Via MV3 Chipset
20GB IBM 7,200 RPM HDD
230w PSU
I could not alter the FSB/PCI ratio as this was a Super 7 board, but, the following AGP cards were tested at 74MHz AGP with absoluelty no problems whatsoever:
. Voodoo 3 3000 (hot!)
. Geforce 2 Ultra
. Gefroce 4 MX 400
I tried a Geforce 4 Ti 4200, and like you it worked in 2D bu no in 3D. I beleive it could be the card and/or your power supply that is the problem. You know your CPU can hit the high MHz, and the K6-III CPU's aren't picky about running at higher bus speeds - it's the other components like the video card and the AGP port or PSU that could be the problem. Also, having to disable the L2 cache on faster bus speeds means that the cache chips aren't fast enough - this may not be the best SS7 board to overclock with.
Socket 7 never really was designed to run AGP, and most boards had a hard enough time running stock AGP cards. Only a few could actually remain stable in operation.
I would definatly get a card that will make the most of type of CPU you have - even if at the end of the day you're stuck with standard AGP speeds. From testing games like GTA Vice City, NFS Underground, I found a huge improvement over the K6-2 but unfortunately, the instant the screen gets rammed you just don't have the FPU power or the bandwidth available to keep the frame rates high. In other words, it's not resolution that's a problem because of the card you're running, but the CPU power at hand. So you need a card that scales well with slower processors.
I was previously an nVidia fan until they started screwing around with naming conventions and driver issues, so there may be a Radeon card that would be better for you, as they tend to give much better performance when FSAA and AF is switched on.
Then again, for £60 in the UK I managed to get an Asrock board with a Duron 1800 that I ramped upto 2100MHz with an OC 128MB GF4 Ti 4200. I'm not being negative about that K6-III because for general use they are very good and I would imagine that yours goes like a bat outa hell, but compared to even a "budget" Duron, there's a world of difference for games. You could be buying a card to run modern games and be dissapointed. Games like Call of Duty are very feasible on that chip you have there, but the likes of Far Cry even with a fast card are not recommended.
So in summary, I think it could be a Matrox, motherboard or PSU issue. You would get a good return on that CPU on eBay, promoting it's overclocking ability..
Hope this helps.