Sachverhalt:
A. Der deutsche Staatsangehörige X._, geb. 1952, erhielt von den Behörden des Kantons Thurgau am 9. Februar 1999 eine Aufenthaltsbewilligung, um seiner Tätigkeit als Geschäftsführer der in W._ domizilierten A._GmbH (später B._ GmbH) nachzugehen. Im Laufe seines weiteren Aufenthaltes in der Schweiz war X._ jedoch auch bei anderen Gesellschaften als Geschäftsführer bzw. als Verwaltungsrat aktiv, so beispielsweise bei der C._AG und der D._AG.
Ende 2005 wurde X._ in Untersuchungshaft genommen und im Februar 2006 an die Bundesrepublik Deutschland ausgeliefert. Vom Landgericht S._ wurde er am 6. September 2006 wegen besonders schwerer Untreue in drei Fällen sowie damit zusammenhängend wegen Bestechung im geschäftlichen Verkehr in neun Fällen zu einer Freiheitsstrafe von vier Jahren verurteilt. Hintergrund seiner Verhaftung und seiner Verurteilung bildeten die Aktivitäten von X._ und der von ihm dominierten A._GmbH bzw. C._AG im Bereich des Motorsportsponsorings: Für die deutsche Chipherstellerin Z._AG sollten sie Werbeflächen auf Rennfahrzeugen an sog. Co-Sponsoren untervermieten. Die Zahlungen dieser Co-Sponsoren in Höhe von rund EUR 1.3 Mio. leitete X._ indes nicht an die Z._AG weiter, sondern nutzte sie teils zu eigenen Zwecken, teils finanzierte er damit private Renneinsätze von zwei Vorstandsmitgliedern der Z._AG, um sich deren Gunst zu sichern. Den gleichen Vorstandsmitgliedern zahlte er zudem Barbeträge in beträchtlicher Höhe aus.

Den Akten ist zu entnehmen, dass gegen X._ auch ein Strafverfahren wegen des Verdachtes auf ungetreue Geschäftsbesorgung im Zusammenhang mit der Tätigkeit der D._AG eröffnet wurde. Gegenstand desselben waren Vorwürfe einer Privatperson betreffend Unregelmässigkeiten bei der Veräusserung der von X._ in V._/TG erstellten Eigentumswohnungen. Mit Verfügung des Untersuchungsrichteramtes des Kantons Thurgau vom 4. Februar 2009 wurde das Verfahren an die Staatsanwaltschaft S._ abgetreten. Diese zog in Erwägung, dass X._ wegen anderen Straftaten durch das Landgericht S._ am 25. September 2006 zu einer Gesamtfreiheitsstrafe von vier Jahren verurteilt worden sei und die Strafe, die wegen der neu angezeigten Tat verhängt werden könnte, demgegenüber nicht beträchtlich ins Gewicht fiele. Aus diesem Grund sah die Staatsanwaltschaft S._ mit Verfügung vom 27. Januar 2009 von der Verfolgung ab.
Am 13. Juli 2007 wurde über die C._AG der Konkurs eröffnet, wobei das Verfahren am 10. September 2007 mangels Aktiven eingestellt wurde. Am 30. November 2006 bzw. am 2. August 2007 wurden die ebenfalls von X._ beherrschten B._GmbH (vormals A._GmbH) und D._AG mangels verwertbarer Aktiven von Amtes wegen gelöscht.
B. Mit Schreiben vom 11. Januar 2007 informierte das Migrationsamt des Kantons Thurgau X._, dass seine Aufenthaltsbewilligung für die Schweiz infolge Landesabwesenheit von über sechs Monaten Dauer erloschen sei. Nach der vorzeitigen Haftentlassung von X._ im September 2007 ersuchte dessen Rechtsvertreter Y._, namens seiner Immobiliengesellschaft M._AG, am 5. Juni 2008 um die erneute Erteilung einer Aufenthaltsbewilligung EG/EFTA an X._: Dieser solle als "Assistent der Geschäftsleitung / Projektleiter" beschäftigt werden. Das Migrationsamt des Kantons Thurgau lehnte das Gesuch am 19. September 2008 unter Hinweis auf die Delinquenz von X._ ab.
C. Gegen die Verfügung des Migrationsamtes rekurrierte X._ ohne Erfolg beim Departement für Justiz und Sicherheit des Kantons Thurgau. Danach beschwerte sich X._ beim Verwaltungsgericht des Kantons Thurgau. Dieses wies die Beschwerde mit Entscheid vom 11. November 2009 ab.
D. Mit Eingabe vom 22. Dezember 2009 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt im Wesentlichen die Aufhebung des vorinstanzlichen Entscheids und die Erteilung einer Aufenthaltsbewilligung EG/EFTA für die Dauer von fünf Jahren zur Ausübung einer Erwerbstätigkeit. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Migrationsamt und das Departement für Justiz und Sicherheit des Kantons Thurgau sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Thurgau beantragt, es sei die Beschwerde abzuweisen, soweit darauf eingetreten werden könne.
Erwägungen:
1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Als deutscher Staatsangehöriger kann sich der Beschwerdeführer auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681) berufen, welches ihm einen grundsätzlichen Anspruch auf Erteilung einer Aufenthaltsbewilligung einräumt (vgl. Art. 4 FZA; Art. 6 Abs. 1 Anhang I FZA). Die Beschwerde ist daher zulässig. Als Adressat des angefochtenen Entscheids ist der Beschwerdeführer gemäss <ref-law> zur Beschwerdeführung legitimiert. Auf das im Übrigen form- und fristgerecht eingereichte Rechtsmittel (Art. 42 und Art. 100 Abs. 1 BGG) ist daher einzutreten.
2. Die Beurteilung der vorliegenden Angelegenheit richtet sich grundsätzlich nach dem Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20). Im Anwendungsbereich des FZA hat das AuG allerdings nur insoweit Geltung, als das FZA keine abweichende Bestimmung enthält oder das AuG günstigere Bestimmungen vorsieht (Art. 2 Abs. 2 AuG), was hier nicht der Fall ist.
3. Gemäss Art. 4 FZA i.V.m. Art. 6 Abs. 1 Anhang I FZA hat ein Arbeitnehmer, der Staatsangehöriger einer Vertragspartei ist und mit einem Arbeitgeber des Aufnahmestaates ein Arbeitsverhältnis mit einer Dauer von mindestens einem Jahr eingegangen ist, Anspruch auf Erteilung einer Aufenthaltserlaubnis mit einer Gültigkeitsdauer von mindestens fünf Jahren, gerechnet ab dem Zeitpunkt der Erteilung der Erlaubnis.
Wie das Verwaltungsgericht zutreffend ausgeführt hat, gilt dieser Anspruch jedoch nicht absolut. Er kann eingeschränkt werden, wenn von der ausländischen Person eine hinreichend schwere und gegenwärtige Gefährdung der öffentlichen Ordnung, Sicherheit oder Gesundheit ausgeht (vgl. Art. 5 Anhang I FZA). Auf die umfangreichen Erwägungen der Vorinstanz sowie auf die in diesem Zusammenhang ergangene bundesgerichtliche Rechtsprechung kann verwiesen werden (E. 2.2 des angefochtenen Entscheids; <ref-ruling> E. 4.1 und E. 4.2 S. 19 f.; <ref-ruling> E. 3 S. 497 ff.; <ref-ruling> E. 3.1 S. 179 f.; <ref-ruling> E. 6 und E. 7 S. 220 ff., jeweils mit Hinweisen).
4. Der Beschwerdeführer bestreitet, dass von ihm bzw. von seinem Aufenthalt in der Schweiz eine schwere gegenwärtige Gefährdung der öffentlichen Sicherheit und Ordnung ausgehe. Er verweist auf seine vorzeitige, bedingte Haftentlassung nach Verbüssung der Hälfte der Strafe und betont, dass hierfür gemäss den einschlägigen Bestimmungen des deutschen Strafgesetzbuches besonders günstige Umstände und mithin eine sehr vorteilhafte Rückfallprognose erforderlich seien. Insbesondere verfüge er über intakte soziale Bindungen: Zwar habe er sich von seiner früheren Lebenspartnerin getrennt, doch pflege er zu ihr sowie zur gemeinsamen Tochter weiterhin einen guten Kontakt. Sodann sei er zwischenzeitlich eine neue Beziehung zu einer in der Schweiz aufenthaltsberechtigten deutschen Staatsangehörigen eingegangen, mit welcher er auch einen gemeinsamen Sohn (geb._2009 in S._) habe. In beruflicher Hinsicht habe er sich nach seiner Haftentlassung mit einer Einzelfirma im Bereich Immobilienverwaltung selbständig gemacht und er erziele aufgrund dieser Tätigkeit ein stabiles Erwerbseinkommen. Vor seiner Auslieferung an die BRD habe er sich bereits während sieben Jahren in der Schweiz aufgehalten und sich hier als selbständig Erwerbender und Inhaber diverser Firmen sowohl gesellschaftlich als auch wirtschaftlich integriert.
5. Die Ausführungen des Beschwerdeführers überzeugen nicht:
Seine Verurteilung durch das Landgericht S._ lässt den Beschwerdeführer in einem ausgesprochen schlechten Licht erscheinen: Dem Strafurteil ist zu entnehmen, dass er planmässig und über mehrere Jahre hinweg delinquierte und der geschädigten Unternehmung dadurch einen äusserst beträchtlichen Vermögensschaden zufügte. Dieses Verhalten und die gegen den Beschwerdeführer verhängte Freiheitsstrafe von vier Jahren deuten auf ein sehr schweres Verschulden und eine ganz erhebliche kriminelle Energie hin. Dass er die in Deutschland verhängte Strafe nicht vollständig verbüssen musste, ändert daran nichts: Dem Beschluss der Strafvollstreckungskammer des Landgerichts U._ vom 4. September 2007, mit welchem die Verbüssung des Strafrests zur Bewährung ausgesetzt wurde, kann entnommen werden, dass hierfür namentlich auch Umstände als massgeblich erachtet wurden, welche bei der Festsetzung des Strafmasses bereits berücksichtigt worden waren (Kooperationsbereitschaft, Geständigkeit).
Entgegen der Auffassung der Vorinstanz darf auch der gegenüber dem Beschwerdeführer erhobene Vorwurf der ungetreuen Geschäftsbesorgung im Zusammenhang mit der Tätigkeit der D._AG mitberücksichtigt werden, selbst wenn dieser von der Staatsanwaltschaft S._ nicht materiell gewürdigt wurde: Vorliegend geht es nicht darum, dem Beschwerdeführer eine strafrechtliche Verfehlung zu unterstellen. Dem Vorwurf kommt aber insoweit eine gewisse Bedeutung zu, als er aufzeigt, dass sich die Strafverfolgungsorgane schon wieder mit dem Beschwerdeführer und seinen Aktivitäten befassen mussten und dieser ein Verhalten an den Tag legt, das von Drittpersonen - zu Recht oder zu Unrecht - als kriminell erachtet wird. Diesem Umstand darf bei der Prüfung der Legalprognose mit einer gewissen Zurückhaltung Rechnung getragen werden, ohne hierdurch die Unschuldsvermutung zu verletzen (Urteil 2C_596/2009 vom 23. April 2010 E. 6; 2C_561/2008 vom 5. November 2008 E. 5.3; jeweils mit Hinweisen).
Auch die nun geplante Betätigung des Beschwerdeführers in der Schweiz lässt ernsthafte Zweifel an seiner zukünftigen Deliktsfreiheit aufkommen: Gemäss Arbeitsvertrag vom 17. Juli 2008 gehört zu den ihm zugedachten Tätigkeitsgebieten insbesondere die Kunden- und Objektakquisition und -betreuung. Gegenüber dem Migrationsamt liess der Beschwerdeführer sodann ausführen, dass er ein erfahrener Marketing- und Vertriebsexperte sowie ein gleichermassen ausgewiesener Immobilienfachmann sei, welcher zudem über ein ausgedehntes und ausgezeichnetes Beziehungsnetz zu namhaften Persönlichkeiten aus Wirtschaft und Sport, insbesondere im deutschsprachigen Europa, Grossbritannien und den USA verfüge. In diesem Zusammenhang hat das Verwaltungsgericht allerdings zutreffend erkannt, dass gerade solche spezifischen persönlichen Kontakte den Beschwerdeführer in der Vergangenheit zu Straftaten verleitet haben, wie die Verurteilung durch die deutsche Strafjustiz zeigt. Zu Recht schloss die Vorinstanz daraus auf eine Gefahr, dass der Beschwerdeführer auch bei der geplanten Tätigkeit als Vermittler von Immobilien wieder zu kriminellen Machenschaften veranlasst wird: Unabhängig davon, ob es nun Werbeflächen auf Rennfahrzeugen oder Liegenschaften sind, die akquiriert bzw. verkauft werden sollen, bergen solche Vermittlungstätigkeiten regelmässig die Gefahr in sich, dass die damit verbundene Vertrauensstellung vom Vermittler zu dessen eigenen Gunsten ausgenützt wird. Als besonders akut erscheint diese Gefahr jedoch dann, wenn ein Vermittler - wie vorliegend der Beschwerdeführer - durch sein bisheriges Geschäftsgebaren bereits seine mangelnde Vertrauenswürdigkeit unter Beweis gestellt hat.
Bei dieser Sachlage durfte die Vorinstanz von einer hinreichend schweren und gegenwärtigen Gefährdung der öffentlichen Ordnung ausgehen.
Dass die Verweigerung der Aufenthaltsbewilligung für den Beschwerdeführer eine besondere Härte bedeuten würde und deshalb unverhältnismässig sein könnte, ist nicht ersichtlich: Er ist deutscher Staatsangehöriger und hat sich während des grössten Teils seines Lebens in der BRD aufgehalten. Gemäss seinen Angaben (vgl. E. 4 hiervor) wohnt er gegenwärtig in T._ bei S._ und betreibt dort eine Einzelfirma im Bereich Immobilienberatung, mit welcher er ein stabiles Erwerbseinkommen erzielen kann. Er scheint demzufolge in seiner Heimat beruflich gut integriert zu sein. Soweit der Beschwerdeführer dagegen behauptet, er habe sich in der Vergangenheit auch in der Schweiz wirtschaftlich integriert, ist festzustellen, dass - soweit ersichtlich - über sämtliche der von ihm einst gehaltenen schweizerischen Gesellschaften der Konkurs eröffnet werden musste bzw. diese mangels verwertbarer Aktiven von Amtes wegen zu löschen waren. Der Hinweis auf die vom Beschwerdeführer behaupteten familiären Bindungen ist ebenfalls unbehelflich: Zum einen ist er mit seiner Partnerin nicht verheiratet, zum anderen ist diese ebenfalls deutsche Staatsangehörige und erst per 1. Juli 2008 in die Schweiz übergesiedelt, so dass ihr grundsätzlich zuzumuten wäre, die Beziehung zum Beschwerdeführer im gemeinsamen Heimatland zu leben. Dass der Beschwerdeführer sich von seinem Domizil in S._ aus an der Betreuung des gemeinsamen Sohnes beteiligt, ist weder dargelegt worden noch ersichtlich. Ebensowenig wurde dargetan, inwiefern die Aufrechterhaltung des persönlichen Kontaktes zum Kind die Erteilung einer dauerhaften Aufenthaltsbewilligung zur Ausübung einer Erwerbstätigkeit bedingt.
Nach dem Ausgeführten ergibt sich, dass die Vorinstanzen dem Beschwerdeführer zu Recht die Erteilung einer Aufenthaltsbewilligung EG/EFTA verweigert haben.
6. Gemäss den obenstehenden Erwägungen ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten offensichtlich unbegründet und daher im vereinfachten Verfahren nach <ref-law> (summarische Begründung / Verweis auf den angefochtenen Entscheid) abzuweisen.
Diesem Verfahrensausgang entsprechend, sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Eine Parteientschädigung ist nicht auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt und dem Departement für Justiz und Sicherheit des Kantons Thurgau, dem Verwaltungsgericht des Kantons Thurgau sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 17. August 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Zähndler