Now that iTunes in the Cloud is available, my iPhone (iOS 5.0) and my MacBook Air (10.7.1 / iTunes 10.5) will show me lists of all the songs I've ever purchased through iTunes. It almost works great: I even found an album I'd completely forgotten I owned.
But I've noticed that at least one album (Muse - Absolution, which is still available on the Canadian iTunes Store), despite having purchased the entire album way back when, only registers a single song (Blackout) as a purchase.
Update: Having looked at a bunch of other albums (and testing downloading one) this is actually rampant across my collection: sometimes all but one, sometimes only a couple of tracks are available from albums that I've purchased, and which are still in the store... Ironically, one of the few albums that will let me download it in its entirety is not in the Canadian iTunes Store!
Update: Sounds like this has been happening since beta, and is still going on.
I received an update from iTunes "support", by which I mean someone they've hired to read pages from their support site to me. The response: tracks which have been removed or modified can no longer be downloaded. Well, many of my tracks haven't been removed, so they must have been "modified". When I asked for clarification as to what modifications cause purchased tracks to no longer register, they provided me with this helpful explanation:
The item has been modified since you purchased it, and no longer available for download. It is not possible to redownload items that has being modified within the store.
Thanks for clearing that up. I'm going to start over with another ticket and see if I can squeeze anything useful out of them.
Update Update: As of today, the Muse album I mentioned has been restored; I can now download all tracks. However, the other affected albums have not changed. Is this because I complained about this album in particular? Do I need to do the same for every other problem purchase? Will this slowly resolve itself over time? Who knows?
Update, Nov. 13, 2011: As of tonight, all my purchased music is once again available. I did not open a case with Support, so I can only chalk this up to fluctuations in the Store that have been resolved (perhaps as we approach the launch of iTunes Match). It's unlikely we'll ever have a definitive answer to this question, though the comments here may be useful to future visitors.