It IS definitely possible to boot to recovery mode.
Even the users with bloody bricked Kindles are able to boot to this mode.
Are you sure you properly followed instructions?
Plug Kindle into USB port.
Press Kindle power switch until LED off.
Press "Magic Key" (Touch = Home button).
Release power switch.
Release "Magic Key".
EDIT: is your battery charged enough?