Internet Recovery ist Teil der Firmware und geht somit auch, wenn die Festplatte/SSD ausgetauscht wurde. Wenn du beim Starten COMMAND+R drückst und keine Recovery Partition gefunden wird, erscheint ein kleines Globus Symbol und er fragt dich nach deinem WLAN Kennwort. Dann dauerts je nach Internetverbindung eine Weile (bei mit ca. 20 minuten) und er startet Lion Recovery - Ich nehme an von einer RAM Disk, da er die SSD die anzufassen scheint.
Wie das mit der Lizenz ist kann ich nicht sagen, er fragt nicht nach dem Store Kennwort oder ähnlichem, insofern nehme ich an, Apple erkennt an der Rechner Modell- oder Seriennummer, dass das aktuelle Air/Pro etc immer mit Lion ausgeliefert wird.
Langer Rede kurzer Sinn, bei den neuen Macs geht Internet Recovery immer, unabhängig davon, was mit der Festplatte/SSD passiert ist.