With background noise? My wife and I had an interesting unintentional experiment regarding this a few weeks ago at a Slowdive concert. She doesn't know the band well and asked me the name of each song as it began and then also asked Google's song identifier service. I knew all of them and Google couldn't even produce an answer, incorrect or not. Either because of the crowd noise or a live version is sufficiently different from any recorded example it has heard before.