How to restore OS X drive to factory defaults?
I booted into Internet Recovery Mode, erased the entire hard drive, and re-installed Mac OS X. This will reinstall the OS that came with the computer, recreate EFI and Recovery Mode partitions, and set CoreStorage volumes as if everything is set from factory defaults. 

After this Recovery Mode works as expected.