From my understanding the "what song is playing" apps/services essentially have a big database of music stored in a special hash function. When you record the music it converts it into a hash, then compares it to the database.
Could these databases and algorithms be open source? Absolutely. Would it be really hard or expensive to maintain the database distribution or hosting? Definitely. Would music rights holders allow an open source project to have access to their music libraries to put into the database? Probably not... I would think that the services that do this have big agreements with rights holders that open source would not be able to get.
I think that's true about being expensive/difficult to maintain, but while IANAL, a hash of music is not the music itself, something that can be converted to music, or in any way protected by copyright AFAIK.
part where I spend other people's time proposing a feature I'm not willing to spend time to implement
Perhaps there could be an optional setting that lets you contribute to a crowdsource thing when people rip their cds with open source software and get the metadata from MusicBrainz (those that still buy cds)? Seems pretty do-able actually.
part with unfounded patent speculation
Maybe there is a patent or something keeping that feature from being added to the databases and programs?