One tiny little joke and next thing you know, you're the Thought Police.
To answer the question, yes, Intel's QRE labs can usually make an educated guess whether or not a CPU was overclocked - it's a matter of statistics though. A processor that fails at 550MHz is probably going to fail in a different way than one that fails at 733MHz. Every CPU that is sent back to Intel is characterized as to failure mechanism by a tester machine, a technician or an engineer (in that order). They are sorted by what they failed due to, and so you start to see a statistical relevance between failure mechanisms and frequency.
Anyway, this will happen long after you have received your new one, and Intel doesn't go back after follow up after the fact. Besides, it sounds like what went wrong was due to the attachment of a 3rd party cooling system (which is a violation of warranty on a retail processor), and this should be fairly obvious just by looking at it so if you want to worry about anything, I'd worry more about that. But you don't need to worry - Intel generally takes them back no matter what unless there is obvious physical damage to the part (ie. it looks like spent a night in the BBQ) and even then Intel usually takes them back.
But in any case, I'm a designer, not a member of the local Thought Police. I'm cetain that you'll have no problem returning it. In the exceedingly unlikely event that you do, email me and I'll see if I can't help from the inside.