… even if i downloaded all of them from the iTunes Store.

Well - most likely you have stored your iTunes library on a NAS or something similar. This won't work. 
matchTag needs the whole file to function properly - not like iTunes which does a kind of "streaming" when playing the songs. A standard network infrastructure is not able to deliver the whole file(s) as fast as matchTag needs them… matchTag cannot read the internal song ID of the file and is therefore not able to recognise the song.

Just copy your library to a local hard drive and try again - the result should be way better now.

Is this article helpful for you?