Look, it's boneheaded to worry about this. Almost everyone has some music on their computer that they acquired "illegally", if only from having ripped a friend's CD or using a flash drive to swap songs.
Similarly, if you go back in time, it would be hard to find a music collection that didn't have some cassette copies that weren't strictly speaking legit.
And downloading copyrighted music from the internet was not always illegal everywhere. When I lived in Canada, it was judged to be legal (although the law has since been changed). That means it will be impossible to in practice judge what is legit and what is not.
Given these fact, the point is that no company is going to offer a product that entraps almost all of its users and subjects them all to legal action and massive fines. Ask yourself whether you would ever again purchase anything from a company that did that to you or allowed that to happen to you. Work out how much money you have given Apple over the past ten years, and then ask yourself whether any sane company would want to lose that income just to enrich lawyers and the recording industry.
It's not going to happen.
In addition, there are different kinds of "illegal" music, including:
Music that is no longer offered for sale anywhere. For example, I have quite a few of copies things that you just can't buy any more, and which I would immediately buy if I could (since I would rather have the CD in most cases). This includes music that people have digitally copied from LPs that they owned.
Music that was never officially released, such as bootlegged concert recordings. The internet has made these much less of a big deal to musicians than they used to be. In the old days, you had to pay the bootlegger for them, and the bootlegger would not pay the artist. Now nobody pays, so musicians don't care as much (many did not care about non commercial concert taping anyway). Moreover, the people who collect these things tend to be the rabid fans, who have all the commercially available material anyway, and who would instantly buy it if it were officially released. Case in point: Led Zeppelin released a triple disc set of one of their concerts that had been widely bootlegged for years (because it was a really good concert). Everyone I know who had the bootleg bought the official release on the day it came out (it's sitting in my CD rack, along with every other CD they ever released).
It's just not worth anyone's time chasing this stuff up, even though it is technically illegal.
iTunes Match is a sign that the music companies are finally getting it. What we need is a model where people who are willing to pay for music buy it, and where the amount of piracy that goes on is offset by charging users a yearly fee. I thought a small broadband tax would solve this, but Apple appears to have hit on a smarter solution. I bet it isn't costing Apple anywhere near $25 a year per user to back up your library (given the way that Match works). What we are doing is paying the record companies a small fee to look the other way when it comes to small time non-commercial piracy. It's in everyone's interest for it to be this way. They get paid and we get a decent backup service and left alone.
And before anyone calls me a pirate. I own about 1700 CDs and have bought about 4000 tracks from iTunes over the past few years. Like most people I have some music that is "illegal" in the various senses described above. I thought it might be a lot, but getting iTunes to count it revealed that it was a very small percentage of the music I own. In this I don't think I'm too different from most people who like music.