Sorry to bring the bad news....
I had an AMD K6/233 that did the same thing (minus the overheat episode)
The Manufacturer's TS agreed with me that the ProC's L1 was bad , and instead of making me ship the darn thing off to them , they agreed to send me a new CPU (after I had already changed out the MoBo - on their reccomendation)
I was on a first name basis with the service manger [Mr. Mike Singfield] @ LegendMicro back then ...

Due to the overheating , you more than likely FRIED the L1 cache on the CPU....
Buuummmer!
You can also run MeMTesTx86 to VERIFY that the CPU's L1 is toast.
There are many configurations available to test with/without CPU cache .
Hopefully you have a less expensive AMD CPU instead of a higher priced Intel !!!!!
I'd bet money on this one!!!

Robert