Sachverhalt:
A. Mit öffentlicher Urkunde über eine Kindesannahme vom 28. Juni 1957 nahm B.X._ sein Pflegekind A.Y._ (Beschwerdeführer) als sein Kind im Sinn von aArt. 264 ff. ZGB an. Seine Ehefrau C.X.-Z._ erteilte ihre Zustimmung.
Mit Schreiben vom 18. September 1965 teilte der Sozialdienst Kehl/D B.X._ im Zusammenhang mit dem Einbürgerungsgesuch für den Beschwerdeführer mit, der Adoptivvertrag sei zufolge eines Formfehlers unwirksam. Es sei daher unumgänglich, in Deutschland einen neuen Vertrag abzuschliessen. Mit Urkunde des Notariats Kehl/D über den Kindesannahmevertrag vom 3. Dezember 1965 nahmen die Eheleute B._ und C.X._ den Beschwerdeführer als gemeinschaftliches eheliches Kind an Kindes statt an.
B. Am 18. Januar 2007 verstarb C.X._. Mit Schreiben vom 31. Januar 2008 teilte die Aufsichtsbehörde dem Willensvollstrecker mit, die Kindesannahme vom 3. Dezember 1965 werde in der Schweiz nicht anerkannt.
Mit Verfügung vom 30. Januar 2009 wies das Departement Volkswirtschaft und Inneres das Begehren des Beschwerdeführers um Anerkennung der Adoption vom 3. Dezember 1965 ab.
Die hiergegen erhobene Beschwerde wies das Obergericht des Kantons Aargau am 23. September 2009 ab.
C. Gegen dieses Urteil hat der Beschwerdeführer am 24. April 2009 eine Beschwerde in Zivilsachen erhoben mit dem Begehren um dessen Aufhebung und Anerkennung sowie Vollstreckung der Adoption durch C.X._ in der Schweiz, insbesondere durch Eintrag in den schweizerischen Zivilstandsregistern. Mit Vernehmlassung vom 1. Juli 2009 hat sich das Obergericht zu den Noven im Zusammenhang mit der Streichung auf dem Original des Familienscheines vom 29. Oktober 1965 geäussert. Das Bundesamt für Justiz hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid (Art. 75 Abs. 1 und Art. 90 BGG). Im Streit liegt ein mit einem Anerkennungsbegehren verbundenes Gesuch um Eintragung einer Abstammung kraft Adoption, mithin eine Gestaltungsklage betreffend den Personenstand (<ref-law>; Art. 7 Abs. 2 lit. m ZStV); in diesem Zusammenhang ist die Beschwerde in Zivilsachen gegeben (Art. 72 Abs. 2 lit. b Ziff. 1 und 2 BGG).
2. Umstritten ist die Anerkennungsfähigkeit der am 3. Dezember 1965 in Kehl/D erfolgten Adoption.
2.1 Diese Adoption erfolgte vor Inkrafttreten des IPRG am 1. Januar 1989. Aufgrund der intertemporalrechtlichen Bestimmung von <ref-law>, wonach sich die Wirkung früherer, aber auf Dauer angelegter Sachverhalte oder Rechtsvorgänge nach Inkrafttreten der IPRG nach dem neuen Recht richtet, bemisst sich auch die Anerkennung einer ausländischen Adoption in der Schweiz nach dem IPRG, selbst wenn sie früher stattgefunden hat (VOLKEN, Zürcher Kommentar, N. 18 und 33 zu Art. 196-199; GEISER/JAMETTI GREINER, Basler Kommentar, N. 31 zu Art. 196; DUTOIT, Commentaire LDIP, N. 2 zu Art. 196-199). Ohnehin würde sich nach dem damaligen internationalen Privatrecht (vgl. dazu BAECHLER, Das neue materielle und internationale Adoptionsrecht der Schweiz, in: Zeitschrift für Zivilstandswesen 1972, S. 327) nichts anderes als das nachfolgend für die Rechtslage gemäss IPRG Dargestellte ergeben, dass nämlich Anknüpfungspunkt nur die Staatsangehörigkeit des Adoptierenden, nicht aber des Adoptierten sein kann.
<ref-law> regelt die (in Art. 25 f. IPRG in allgemeiner Weise geordnete) Anerkennungszuständigkeit für Adoptionen und beantwortet die Frage, von welcher ausländischen Behörde die Entscheidung ausgegangen sein muss, damit sie in der Schweiz Wirkung erlangen und anerkannt werden kann (vgl. <ref-ruling> E. 4 S. 90; <ref-ruling> E. 4.1 S. 471). Dieser Bestimmung zufolge werden ausländische Adoptionen in der Schweiz anerkannt, wenn sie im Staat des Wohnsitzes oder im Heimatstaat der adoptierenden Person oder der adoptierenden Ehegatten ausgesprochen worden sind. Ausserhalb dieser Konstellationen wird eine im Ausland vollzogene Adoption durch Ehegatten mit Wohnsitz in der Schweiz nicht anerkannt; vielmehr müsste sie diesfalls in der Schweiz "wiederholt" werden (RASELLI/HAUSAMMANN/MÖCKLI/URWYLER, Ausländische Kinder sowie andere Angehörige, in: Ausländerrecht, 2. Aufl., Basel 2009, N. 16.106).
Die Wirkungen der Anerkennung gehen dahin, dass der ersuchte Staat die Geltung fremder Rechtsakte auf seinem Hoheitsgebiet duldet (<ref-ruling> E. 3a/cc S. 86). Eine im Ausland ergangene Entscheidung kann in der Schweiz grundsätzlich keine weitergehenden Wirkungen entfalten als im Urteilsstaat; die Anerkennung kann nur Wirkungen erstrecken, nicht aber neue schaffen (<ref-ruling> E. 5.2.3 S. 635). Die Anerkennung einer ausländischen Adoption begründet deshalb kein neues Kindesverhältnis, sondern erstreckt die Wirkungen dieses Rechtsaktes auf die Schweiz (<ref-ruling> E. 3.3 S. 370).
2.2 Der Beschwerdeführer behauptet insbesondere, C.X._ habe im Zeitpunkt der Adoption noch die deutsche Staatsbürgerschaft besessen, weshalb diese im Heimatstaat eines adoptierenden Elternteils erfolgt und deshalb gemäss <ref-law> in der Schweiz anerkennungsfähig sei.
Das Obergericht hat diesbezüglich erwogen, am 3. Dezember 1965 hätten beide Elternteile die schweizerische Staatsbürgerschaft besessen. Weil das Doppelbürgerrecht in der Schweiz erst seit dem 1. Januar 1992 ohne Einschränkungen erlaubt sei, müsse davon ausgegangen werden, dass C.X._ mit ihrer Einbürgerung auf ihr deutsches Bürgerrecht habe verzichten müssen.
2.3 Dieser Schluss kann so nicht gezogen werden. Massgeblich für das Schicksal des deutschen Bürgerrechts ist nicht das schweizerische, sondern das deutsche Recht, und im Übrigen ist nicht allein die damalige deutsche Rechtslage entscheidend, sondern enthält die Frage, ob C.X._ im Zeitpunkt der Adoption die deutsche Staatsbürgerschaft noch besass, auch eine Tatkomponente:
Zunächst steht fest, dass die im Jahr 1924 im damals zu Deutschland gehörenden Schlesien als Z._ geborene C.X._ ursprünglich deutsche Staatsbürgerin war. Sodann ist bekannt, dass sie in der Schweiz nicht ein ordentliches Einbürgerungsverfahren durchlief, welches seinerzeit in der Regel tatsächlich eine Verzichtserklärung auf das bisherige Bürgerrecht bedingte, sondern dass sie das Schweizer Bürgerrecht aufgrund der bis Ende 1991 bestehenden Gesetzeslage (vgl. Revision des BüG vom 23. März 1990, AS 1991 1034; zur vorangehenden Gesetzeslage BBl 1987 III 293,295) automatisch durch die am 22. Dezember 1951 erfolgte Heirat mit dem Schweizer Bürger B.X._ erwarb.
Ob dieser automatische Erwerb nach dem damaligen deutschen Recht zwingend zum Verlust der deutschen Staatsbürgerschaft führte, ist nicht bekannt. Aber selbst aus dem Wissen um einen allfälligen Rechtsverlust nach der damaligen Gesetzeslage in Deutschland liessen sich noch keine verbindlichen Schlüsse ziehen: Offensichtlich konnten die schweizerischen Behörden nicht über das deutsche Bürgerrecht disponieren; vielmehr lag es an den deutschen Stellen, über dessen Bestand zu befinden. Eine Aberkennung hätte aber zunächst vorausgesetzt, dass die deutschen Behörden von der Heirat und dem damit verbundenen Erwerb des Schweizer Bürgerrechts erfahren haben, was nicht zwingend ist. Sodann ist denkbar, dass die Behörden zwar davon erfahren, aber C.X._ das deutsche Bürgerrecht z.B. aus Billigkeitserwägungen belassen haben.
Ob C.X._ ihr deutsches Staatsbürgerrecht im Zeitpunkt der Adoption im Dezember 1965 noch besass oder nicht, stellt ein entscheidrelevantes Sachverhaltselement dar, ohne das es dem Bundesgericht nicht möglich ist, die sich im Zusammenhang mit dem Anerkennungs- und Vollstreckungsbegehren stellenden, insbesondere die im Zusammenhang mit <ref-law> stehenden Rechtsfragen adäquat zu beantworten. Zumal es möglich sein sollte, die zu dieser Feststellung notwendigen Unterlagen beizubringen, ist die Sache zur Vervollständigung des Sachverhaltes an das Obergericht zurückzuweisen.
2.4 Bei dieser Sachlage werden die weiteren Rügen des Beschwerdeführers, insbesondere diejenige im Zusammenhang mit dem Vertrauensgrundsatz, vorderhand gegenstandslos.
3. Der Beschwerdeführer ist im Grundsatz durchgedrungen, weshalb er seitens des Kantons Aargau zu entschädigen ist (<ref-law>). Dem Kanton sind keine Gerichtskosten aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. In dahingehender Gutheissung der Beschwerde in Zivilsachen wird das Urteil des Obergerichts des Kantons Aargau vom 23. März 2009 aufgehoben und die Sache zur Sachverhaltsergänzung und neuen Entscheidung im Sinn der Erwägungen an das Obergericht zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Aargau hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien schriftlich mitgeteilt.
Lausanne, 21. August 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Möckli