Just adding an update to this. I had the chip running at 4.0GHz for a while, but it seemed to degrade gradually, so that it was unstable even at lower multipliers. I had a tuning plan for it, and have just put my exchange chip in the machine. I followed the ASUS OC guidelines, put it to 1.3V and 45 multiplier, and its nice and happy. So looks like that last chip was just a really nasty one, or my faulty Deluxe did something to it.
If anyone wants to know, the batch number of the old chip was L427C525. It was a MALAY chip.
Now I just need to figure out how to get adaptive voltage to work.