By coincidence I just found out that .m3u playlist files don't support unicode characters. I was editing the tags of some albums of the Turkish artist Tarkan, and yes, there are a lot of unicode characters in those titles. After saving the album to a .m3u file, which I always do, a lot of tracks couldn't be found.
I tried to change one track in notepad and save that as Unicode but then the .m3u file doesn't work anymore. From Winamp it's possible to save that exact same album as a .m3u8 file, which solves the whole problem.
My question is: Wouldn't be a good suggestion to add the m3u8 support to MP3Tag?