I'm porting the songprint algorithm to Java ... It converts MP3 to a PCM bitstream, so combining songprint with file hashing should allow us to identify all the scenarios we need. I have no idea what the performace of songprint is like, though.