The damndest thing: I am checking the files that are missing artwork now. I check them with mp3tag and the artwork is missing there as well! Of some of these files I am absolutely sure that the artwork was there and showing in Winamp.
Musicbee didn't remove the artwork, did it? It's not like iTunes that changes your tags and everything without asking, is it?
For one album I chose "edit"<shift-enter> and there appeared to be an invalid picture on top of the actual artwork. I removed the invalid picture and the album art showed up. Even weirder: this album was CD1 of a 2 CD album. CD2 didn't show artwork at first, but when I had removed the invalid file from CD1, the artwork on CD2 showed up as well.