Jede App bekommt eine global eindeutige Identifikationsnummer (Global-Unique-ID; GUID). Das ist diese AppID, über die man die App auch im Store findet, beispielsweise ist die GUID ed27a07e-af57-416b-bc0c-2596b622ef7d die App Windows-Karten. Wenn eine App verloren gegangen ist, dann taucht in jenen Menüs nicht mehr der App-Name sondern die AppID als GUID auf. Aber das ist bei Dir nicht der Fall, weil Cortana immer noch aufgeführt wird.
Hast Du unter dem Menüpunkt „Alle Apps“ noch den Eintrag „Suche“?