Have you tried just hitting the the Del or F2 key continuously instead of waiting for those lights to blink (Num Lock Caps Lock Scroll Lock)....
I think that is what you mean to say when you say "keyboard is recognized"?
The post process takes a little while, even if the screen that tell you to press Del or F2 disappears from the desktop, it doesn't mean if you press Del or F2 after that it won't work or hasn't registered as a keystroke when the Keyboard wasn't recognized.
Try it and give it sometime.
Also check and make sure that the Keyboard is plugged into the USB closest to the PS/2 socket at the Top of the Back I/o Panel.