Sounds to me that during cold-boot, the mainboard does not detect the keyboard module properly, but after everything is powered on and has juice going to it, the keyboard will then respond on the reboot.
Could be that it's not the keyboard module that is the issue, but rather a faulty connector or cable on the mainboard.