If we're talking about online lookup, then there's a simple countermeasure: if the system has already seen the same serial number 50 times, or it sees the serial number in Shanghai then fifteen minutes later in Frankfurt, or any number of other heuristics, it'll report that it's a fake. True, this might inconvenience the one legitimate customer who had that original serial number.

Also, you need to make sure that the serial numbers are long and random-looking, so that they are not auto-generated.