I think I found what's going wrong.
It's definitely on Apple's side, but I think they somehow wrongly process the app assets that are bundled within the app archive when they are only made of black/grey/white images.
Basically, greyscale images end up having a wrong gamma correction.
How did I fix it? I added 1/255th of blue to my black part of our greyscale logo.
As an example, here's what our black (main) color value is before and after the "trick"
- Before: #1A1A1A / R:26, G:26, B:26 (dark grey)
- After: #1A1A1B / R:26, G:26, B:27 (still dark grey, but the data says it's 1/255 more blue)
Now since my app icon includes white and some very dark grey that has more blue that red or green, the App Store backend processes it like a color image instead of a greyscale one. And it's now looking good as expected!
Almost invisible difference to the eye when comparing with the non-App-Store-processed image.