Finally! I had the same problem on El Capitan (yes, I'm upgrading now, but I wanted to have a complete El Cap system, including the recovery partition, on a USB key before moving on) and Sierra. Deleting and recreating the partition using that famous script did nothing for me. There should be a sticky somewhere about the necessity of copying the prelinkedkernel (which I guess is prelinked to FakeSMC etc) in order for the recovery partition to function. This information should not be as obscure as it is.
Note that even after this the El Cap partition has an image verification error; this does not appear to affect functionality though.
Anyway, thanks OP! This was the last piece of the puzzle.
ED: In case anybody else is having "launchd exited with code" 1 or 255 when trying to boot from Recovery HD, not having a prelinked kernel may be the issue. It was for me.