I was on iTunes in the "Purchased" section wanting to redownload a couple songs and they weren't there. I checked my purchase history and it shows I purchased it in May of 2012. Why wouldn't it show up as being purchased in iTunes?
As I understand it, the availability of re-downloading Music via iTunes in the Cloud is at the whim of the record company or artist. If either party decides to pull the content from the iTunes Store, you cannot re-download it. This also applies to Books, TV Shows, and Movies but not Apps. Other than backing up offline or signing up for iTunes Match there really isn't a way to ensure that what you bought will be permanently available to download.