"ohne irgendwelche Ansprüche oder Forderungen"  

Der ist gut. Einem nackten Mann kann man nicht in die Tasche greifen....

Ich würde wie folgt vorgehen:

Zuerst ALLE Fakten sammeln (sein Name inkl. beider Nachnamen, sein Geburtsdatum, sein letzter bekannter Wohnort, sein Beruf, wie lange war er wo in der DDR, sonstige Details von ihm). Sprecht nochmal mit allen Betroffenen - der Dame, die die Liäson hatte, evtl. seinem alten DDR-Arbeitgeber (falls möglich). Gibt es Briefe/Fotos von ihm. ALLES zusammentragen.

Wohnt(e) er in einem kleineren Dorf, würde ich versuchen, dort anzurufen, irgendeine Nummer, die sich grad via Internet ermitteln lässt. Hier hilft eventuell das Forum weiter. Auf dem Land / in kleinen Dörfern kennt man sich.

Wohnt(e) er in einer grösseren Stadt, gäbe es verschiedene Möglichkeiten. Zum Beispiel Hinfahren und vor Ort recherchieren
- einen Polizisten fragen, ob dieser mal einen Blick in den Computer werfen könnte (gegen ein Trinkgeld)
-  oder "Arbeitskollegen" suchen (wenn er z. B. in einem Hotel beschäftigt war oder überdurchscnhittliche Fremdsprachenkenntnisse hat (Tourismus), mal ein paar Hotels abklappern, Ärtze fände man in Krankenhäusern,....)
- lässt sich sein Wohnviertel irgendwie eingrenzen, dort mal auf den Bauernmärkten (agromercados) rumfragen und den barrio-CDR konsultieren.
- auf dem "registro civil" (in etwas Einwohnermeldeamt) wird man vorallem als Ausländer kaum Hilfe bekommen, müsste schon ein Mitarbeiter mit sehr grossem Herz sein, dem es egal ist, wenn er seinen Job verliert.
   
Oder man fragt per Mail die Consulteria Juridica (gibt's in jeder grösseren Stadt) um (anwaltschaftliche) Hilfe an (ist kostenpflichtig und nicht gerade günstig).

Wäre gar noch eine alte Adresse bekannt, bringt "ein Brief schreiben" garnix. Der ist ca. 8 Wochen unterwegs und geht auch gern mal verloren. In diesem Fall am besten hinfahren. Die alte Adresse muss ja auch nicht mehr stimmen, dann aber wissen vermutlich alle Nachbarn, wohin der Gesuchte verzogen ist.

Zähl mal auf, welche Fakten und Details Ihr zu ihm habt (ohne Namensnennung). Dann fällt mir/uns vielleicht noch was ein. Z. B.

- Señor Reinaldo X. Y.
- geboren im Jahre bzw. Alter ca.
- aus Cienfuegos, (barrio / calle bekannt oder nicht bekannt)
- arbeitete in einem ostdeutschen Kernkraftwerk von 19xx bis 19yy als ???
- sprach nebst Spanisch gut Deutsch und mittelprächtig Englisch
- es gibt 3,4,5 Briefe von ihm
- Foto liegt vor / gibt es keines
...

Vielleicht fände sich ja dann ein Spanischsprachiger aus dem Forum, der baldmal in der anvisierten Gegend ist und sich dort etwas umhören könnte. Dann spart Ihr Euch zunächst mal eine Reise....

Viel Erfolg und bei Erfolg hier berichten!