Das haben Pixel-Bilder zumeist an sich, dass sie beim vergrößern Qualität verlieren. Wenn du verlustfrei Bilder vergrößern möchtest, benötigst du Vektor-Grafiken. Die wirst du aber für normale Fotos nicht erhalten.
Du schreibst zudem, dass die Bilder bereits gelöscht waren? Wenn du diese wiederherstellst, kann es durchaus sein, dass bereits Bildinformationen verloren gegangen sind. Verwendet man hierfür Programme wie Recuva erhält man vorab eine Information inwiefern die Datei ggf. beschädigt ist bzw. wie der Zustand der Datei ist.
Im Übrigen haben die gängigen Grafikprogramme die Möglichkeit das Kompressionsverfahren bzw. die Qualität beim Speichern festzulegen. z.B. Photoshop:
Das Vergrößern selbst funktioniert übrigens bei manchen Programmen wie Photoshop besser als wenn ich hierzu z.B. Paint von Microsoft verwende.