Hey, sorry for the lack of answers. I worked around the problem by reripping the specific album that wouldn't play on my Clip+ into FLAC. It plays fine, now.
But as I suspected, I have the exact same problem with 3 other albums. If I don't find a solution, I guess I'm gonna rerip them into FLAC as well, but I did what you advised and opened the faulty files in a text editor. They all begin with "OggS" so I guess they don't contain ID3 tags. I tried comparing them with working files, but I didn't spot any significant difference. I mean, they all start with "OggS" and then there's just random characters.
I've only found 3 albums that won't play so far. All the others play fine, and they were all encoded exactly the same way. I really don't see what can cause this.