Acontece que o principal requisito para o Modo de Recuperação é uma partição de recuperação. Normalmente, a partição de recuperação é criada durante a instalação do Mac OSX, mas em alguns casos pode não ser. Se a partição de recuperação não foi criada, o Recovery Mode não pode ser acessado.
Verifique se você tem uma partição de recuperação executando diskutil list
do Terminal e procurando uma entrada para "Apple_Boot Recovery HD" (graças a um Apple SE responde para os passos).
Se você não tiver uma partição de recuperação, você pode criar uma usando o Recovery Partition Creator e um instalador OSX. O instalador é colocado no diretório Aplicativos depois de baixar a atualização da App Store (e é removido após a instalação da atualização). Você pode fazer o download novamente de um instalador da App Store, se você o obteve originalmente por meio da guia Compras.
No meu caso, a instalação do último OSX (El Capitan) criou a partição de recuperação sem nenhum trabalho adicional meu.