That's an interesting problem. Is there any sort of regularity to the machine powering up (a certain delay after shutdown, a particular time of day, a relationship to an external event?)
What symptoms necessitated a mobo/proc swapout? A BIOS flashing virus would be a nasty thing to catch (not very effective, though, as it could only target a particular model board), and I don't think that microcode flashing vulnerabilities have existed for some time.