Assuming it matched the correct songs, I can see a few possibilities.
1. The songs are available in other countries. This means they're in the library, just not for sale individually.
2. Apple has the songs in it's library, potentially as part of a big "package" delivery from a label, and is authorized to match them--even though some licensing may not be in place for individual sales.
3. The songs were available at one time, but for some reason now they are not. Apple would still have the songs in their library and would likely be able to match them.