Die RECOVERY-Funktion soll ja auch dann klappen, wenn sich die Platte verabschiedet hat und man eine fabrikneue eingebaut hat. In diesem Fall ist die RECOVERY-Partition auch nicht mehr vorhanden.
Bei HP muss man die RECOVERY-DVDs selbst erstellen (solange die Platte noch OK ist), alternativ kann man auch einen USB-Stick benutzen, da reicht oftmals einer, wenn er groß genug ist (16 oder 32 GB).
Wie das mit dem Produkt-Key im UEFI ist, kann ich nicht sagen. Wenn Du ein anderes System installierst und dieses den UEFI-Eintrag löscht, ändert o.a., dann klappt das mit dem RECOVERY evtl nicht.
Vorher unbedingt den Produkt-Key von 8.1 auslesen, dazu gibt es Tools.
Wenn auf dem Notebook Win8.1 nicht mehr drauf ist (durch Linux ersetzt), dann darfst Du dieses Win8.1 auf einem anderen PC installieren. Dazu brauchst Du aber eine Install-DVD mit der passenden Version (Core oder Pro).