Eu tive um problema semelhante no meu notebook Asus. A Asus ofereceu ferramentas para armazenar as informações de recuperação em um disco rígido externo (ou DVD), de modo que eu pudesse excluir com segurança a partição de recuperação. Talvez a HP tenha algo parecido?
Editar: está escrito no How-to sobre a recuperação no site de suporte .