Nunca he probado a proteger recovery pero no creo que se pueda.
Al menos, no con el recovery tradicional ya que no tiene opción de escritura con teclado (no vas a poder meter pass)
Si acaso seria con el proyecto de Touch recovery y ni con esas.
Lo mejor seria ponerse en la piel del caco, lo primero que va a hacer es apagar el teléfono y quitar batería, es de cajón.
Quizá, si no es un lumbreras, tendrá la genial idea de romper la tarjeta sim que lleve y poner una suya para ver si está liberado.
En ese momento entra cerberus en acción y manda el aviso a los números de teléfono por cambio de sim.
Todo eso suponiendo que no lo flashee automáticamente, porque si no, no hay nada que hacer.