Alright, I've managed to solve it. My ffmpeg idea was not related - the reason why it worked, however, was that ffmpeg stripped out all existing meta information from the file, and when I added it back, I only added ID3v2 tags, whereas a lot of my files have a mixture of ID3v1, ID3v2 and even APEv2 tags, often all at the same time.

Some further testing revealed that the tags would not always be read if I had more than one meta information type in the file.

Thus the simple solution was to just rewrite all my files' meta information as ID3v2.

An easy way to do this in Windows is to use Mp3tag. You can open a whole directory structure with it, and it will read all subdirectories as well (so you can just select your entire music directory).

Select Tools>Options and then under Tags>Mpeg, set these settings:

In the Write settings:
- Uncheck ID3v1
- Uncheck APEv2
- Check ID3v2 - I selected ID3v2.4 UTF-8 in most cases (edit: it seems that album art seemed to work better with ID3v2.3 UTF-16 in some cases).

In the Remove settings:
- Check ID3v1
- Check APE
- Uncheck ID3v2

Click OK to save the options.

Select Edit>Select All Files and then with all files selected:
- Save (click the floppy disk icon) - this will make sure all files have ID3v2 tags
- Remove tags (the red X beside the Save button) - this will remove all tag types except for ID3v2

After I did this, I copied all files back to the internal memory and let Media Player reindex everything.

After doing this, Media Player had all my tags read and categorized properly.

So it did indeed seem to be some sort of meta information conflict. When I previously was rewriting the tags, I wasn't removing the other tag versions, which is why the files that didn't work continued to not work - until I only wrote one type of ID3 tag.