Hi Matt,
Can you check the BIOS boot settings? Any chance you have Legacy Boot enabled? Are sure that recovery media was created successfully? Thank you in advance.
I guess I didn't "Press any key to boot from CD or DVD..." fast enough. I was confused because the message is in Czech. I don't speak Czech. Why did the recovery media creator set my language to Czech? The language is set to English in Windows I have have no language packs installed. [Insert Twilight Zone theme here]
I have heard this before... Could you go and look into BIOS and make sure your timezone and language is correct? I don't know if that fixes it but I thought that was a solution once (long time ago, I'm getting rusty )
Honestly, you got me attracted to this mystery so I spent several hours walking circles but finally found this funny explanation at the MS KB article:
If there are multiple languages installed, recdisc.exe will select the bootfix.bin file for the first language installed, alphabetically by locale code.