That's correct they can scan the CPUs. Even if you send them a sanded/lapped processor, they can identify it.
The problem here is that they consider the HS to be physically damaged enough.
What you could try to play with is this:
- The processor was not physically damaged.
- The TIM used was Liquid Metal type and this is the reason why the HS looks like this.
- You tried to clean it as much as you could without damaging the processor and this is the result.
- They can identify the processor.
=> The processor was not sanded, those are not sanding marks but TIM residue you didn't want to remove in fear of physically damage it.
Ask them politely to clean it
This is Intel's Warranty Policy for Processors:
http://download.intel.com/support/processors/sb/Limited_Warranty_8.5x11_for_Web_English.pdf
This is the only reason I can find why they rejected it: "where the original identification markings have been removed, altered or obliterated". But technically, the markings have not been removed nor altered nor obliterated, the markings are just below a layer of TIM.
EDIT: Just read the part where you cleaned it with The Stilt's solution. Now it looks way better, just like a CPU with some concrete TIM you find in OEM. If they reject it again because it was previously rejected. Kindly ask them to reconsider since they were wrong the first time and now you managed to clean it better. You could even link them the thread as a last resort.