How to embed cover art into MP4 without errors?
In the Codec Tweak Tool under Miscellaneous > Thumbnails the checkbox for .mp4 was unchecked. After checking it and saving the settings it finally showed the thumbnail.

The Tweak Tool is installed with K-Lite Codec Pack. There are different editions available, I use the Standard edition so I can't talk for the other ones.

Credits for finding the solution: Furty from the same (copied) thread on Super User as a comment