Looking at a dollar bill, I guess the serial-number space is 8 digits plus 2 letters. So naively the chance of any hit with 10^5 bills is 1 in 676000, yeah. (But maybe the serials were smaller then?)

Re the lookup problem, you could initially "hash" all the bills by say the two leading figures, in your first pass.

It's all way stupider than the game-show hack.