Have you verified that the clock dividers are set correctly? I don't know how you set it up when you underclocked the K6s, but if you're using a different FSB than the Pentium MMX then maybe something could have been overlooked in the setup. If PCI is overclocked it might cause that behavior. Could also be a power supply problem, or something else with voltage related jumpering. I know you said it's set to Auto, but I don't know that board and in general those super socket 7 boards tend to have a lot of jumper settings that need to be changed for different CPUs.
I don't know what the CPU support situation is on that board, but if there's any doubt about what CPUs it supports then the K6-2 is more likely to be supported than the K6-3, and should have lower power requirements from the motherboard's onboard regulator, so I'd probably start with the K6-2 for troubleshooting.
If you haven't already, strip down the configuration to be as simple as possible.
What happens if you leave the K6 CPUs set at 200/66 like the Pent MMX?
If you are able, try checking voltages with a multimeter while it's trying to boot, see if anything is low or fluctuating under load.
Any sign of bad capacitors? It could be in a marginally working state where it still works with the MMX but not with a faster K6.