Stolen bikes have long been a lucrative source of income for pawn shops and the less scrupulous indies. Oddly enough its the chains like Cash Converters who would find it easiest to take on such a system.
Personally I think that it could and should work. By implementing a system like this you offer protection in both ways. Once to the original owner of a bike as it would cull the demand for stolen ones and also for the purchaser of a second-hand bike. If there is an onus on the bikeshop to keep and report a record of all second-hand bikes then if their preloved pride and joy turns out to be hotter than Neve Campbell they would have recourse to claim back the cost from the retailer.
I would also like to see the Police create an online registry of stolen bike frame numbers that have been reported to them. Something that can be checked by private purchasers quickly and easily. Then again I would quite like to see some kind of incentive for people who have had their bikes stolen to report the theft to the police.