So the problem seemed to be on an electronic level, with the motherboard unable to supply enough power to the keyboard on a cold boot.
The work-around I found was the following:
In the BIOS (well actually UEFI) enable the option called power on PS/2, or wake on PS/2 or something similar.
This seems to make the motherboard keep the keyboard powered even when the PC is shut down. Then you can start the PC by pressing a key, and in any case the keyboard works directly after booting, no need to reboot.
Let me know if you encounter the same problem and if this solution works for you.