I like the idea of bringing up a selection of songs that it can match to. Of course I can see the record labels saying that that is essentially letting you choose a song other than the one you presumably "own."
Worst case the user could get a different version of the same song (explicit/clean/live/etc). And even if someone did that, would it be a big deal to the record company? It wouldn't give a choice of any song, just ones with close enough waveforms.
Apple needs to either improve their matching significantly or allow users to "help". If using metadata for assistance turns out to be the best way to get the job done, they'd be fools not to use it. And if they don't make significant improvements from how it works now, it's just not going to make it (see MobileMe, which did make improvements but never recovered from the initial terrible bad press).
Heck, I finally was able to get Match working on a second Mac, and it does show my full library. But it's not letting me download anything, not matches or uploads, not even purchases. Looks like either Match or the store (or at least part of it) may be down right now, I'll have to see if it fixes itself soon or if it's something broken I'll have to troubleshoot.