I replaced my black cartridge yesterday with an official one from HP (62). All documents I printed from that moment on are purely black and white. The issue is that grey shades are not printed at all. I ran a printing diagnosis and the grey shades are actually printed properly.
I tried printing from my MacBook (latest drivers) and from my Android phone (latest apps + updates) and it failed in both cases. I don't understand what is causing this. On one hand it doesn't look like a hardware issue because it is able to print grey shades in the printer diagnostics, and on the other hand it doesn't really look like a software issue since everything is the latest version.
I found out what was causing this -- which still feels a bit odd to me -- but my color cartridge was really dry and not operating. I replaced that one as well and it started printing grey shades again.
The printing diagnosis did print the grey shades, but not the grey border around it. Apparently it also requires color in order to print certain types of grey.