So what happened is that I was living in Canada. I bought a bunch (maybe 30-50) songs directly from iTunes over the years. I had them on my iPad mini.
Later on, I was working and living in US, so I changed the country to US and added a US credit card to my iTunes account. Everything was fine.
Then, the iPad mini with Retina display (aka iPad mini 2) came out and I wanted to upgrade to it. Normally, I have nightly backups to iCloud, but since they are (unfortunately) not as thorough, I made a full local backup to my MacBook, and restored it on the new iPad mini with Retina. All the apps and settings transferred fine, but all songs were missing. When I went to "iTunes Song Purchases", it was empty, as it doesn't consider purchases I made in the Canadian iTunes Store as purchases.
I know that if I remembered/knew which songs I bought, I could buy them again and it might not charge me a 2nd time, but it's like playing russian roulette - you have to confirm a purchase and if it matches, you don't pay, else you do. Plus it's a lot of work to find/remember which songs I bought.
At first I was pretty unhappy about it and was gonna try to do something, but then I just gave up on it and moved on. It's not completely Apple's fault, because they have to deal with countries and having separate stores. I wish there was one global store and 1 country and 1 currency and I wouldn't have to deal with this just because I moved to new coordinates, but yeah.