The serial is pretty hard to remove, without it's removal being obvious to anyone that looks, though the brand can be removed or changed - if that happens the serial wouldn't show as stolen.
If there was a lookup for serials then you could check if the bike was stolen, or if the bike was incorrectly branded (serial doesn't match brand), but there isn't a central place for this, unless the (ex)owner registers it on a service such as immobilise.com
The thief had actually given him the serial number of the bike, which he checked in the online police database and it returned no hits. The catch was that the thief slightly altered the serial number so that it wouldn't yield any hits. When he went to actually look at the bike he didn't notice the subtle difference in the serial number and assumed it to be legit.
The OCR-A character set used in the MICR numbers on checks makes it easy to spot a modification like the one in your story.