Sachverhalt:
A. Das Obergericht des Kantons Appenzell Ausserrhoden verurteilte X._ am 21. Januar 2008 zweitinstanzlich wegen mehrfacher Veruntreuung, gewerbsmässigen Betrugs, mehrfachen betrügerischen Konkurses, Gläubigerschädigung durch Vermögensverminderung, mehrfacher Misswirtschaft, mehrfacher Urkundenfälschung sowie Erschleichens einer Falschbeurkundung zu einer Freiheitsstrafe von vier Jahren, unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs.
Gegen dieses Urteil führte X._ Beschwerde ans Bundesgericht, welches diese mit Urteil 6B_794/2008 vom 1. Dezember 2008 teilweise guthiess, den angefochtenen Entscheid aufhob und die Sache zur neuen Beurteilung ans Obergericht des Kantons Appenzell Ausserrhoden zurückwies. Das Bundesgericht erwog zusammenfassend, das Obergericht habe der Verminderung der Schuldfähigkeit fälschlicherweise nur bei der Festlegung der Einsatzstrafe und - entgegen der bundesgerichtlichen Praxis - nicht auch im Rahmen der Strafschärfung infolge Konkurrenz gemäss <ref-law> Rechnung getragen (E. 2.2 und 3.1). Das Beschleunigungsgebot hingegen erachtete das Bundesgericht nicht als verletzt (E. 2.3 und 3.2).
In Nachachtung des Urteils des Bundesgerichts vom 1. Dezember 2008 reduzierte das Obergericht des Kantons Appenzell Ausserrhoden mit Urteil vom 20. April 2009 das Strafmass und bestrafte X._ mit einer Freiheitsstrafe von drei Jahren, unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs.
B. X._ führt Beschwerde in Strafsachen mit den Anträgen, das Urteil des Obergerichts des Kantons Appenzell Ausserrhoden vom 20. April 2009 sei aufzuheben, und die Sache sei im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt den straferhöhenden Einbezug einer seiner Vorstrafen durch die Vorinstanz.
Die Vorinstanz führt im Rahmen ihrer Erwägungen zur Strafzumessung unter Verweis auf ihr Urteil vom 21. Januar 2008 aus, die beiden Vorstrafen des Beschwerdeführers in Deutschland aus den Jahren 1992 und 1994 seien straferhöhend zu veranschlagen. So sei der Beschwerdeführer einerseits mit Urteil des Landgerichts Kleve vom 11. September 1992 wegen mehrfachen Betrugs und mehrfacher Urkundenfälschung zu einer Gefängnisstrafe von zwei Jahren und acht Monaten verurteilt worden und andererseits mit Urteil des Amtsgerichts Tiergarten in Berlin vom 7. Juli 1994 wegen fortgesetzter gemeinschaftlicher Steuerhinterziehung in zwei Fällen mit einer Freiheitsstrafe von drei Jahren und fünf Monaten bestraft worden, wobei die Entscheidung des Landgerichts Kleve miteinbezogen worden sei. Dem relativ langen Zeitablauf seit den Verurteilungen und dem Umstand, dass nur noch diese zwei Vorstrafen sowie der Rückfall zu beachten seien, sei mit einer Straferhöhung von sechs Monaten Rechnung zu tragen (angefochtenes Urteil S. 19 f.).
Der Beschwerdeführer macht insoweit eine Verletzung von Art. 369 Abs. 1 lit. b i.V.m. Abs. 7 StGB geltend. Er bringt vor, die Bestimmung von <ref-law>, wonach aus dem Strafregister entfernte Urteile dem Betroffenen nicht mehr entgegengehalten werden dürften, müsse analog auch auf ausländische Strafurteile Anwendung finden. Das Urteil des Landgerichts Kleve vom 11. September 1992 wäre, wenn im schweizerischen Strafregister eingetragen, gestützt auf <ref-law> nach 15 Jahren, das heisst am 12. September 2007, entfernt worden. Indem die Vorinstanz diese Vorstrafe zum einen straferhöhend und zum andern bei der Prognosebeurteilung berücksichtigt habe, habe sie Bundesrecht verletzt (Beschwerde S. 3 f.).
1.2 Gemäss Art. 3 Abs. 1 lit. e der Verordnung über das Strafregister (VOSTRA-Verordnung; SR 331) werden unter näher bestimmten Voraussetzungen auch Urteile, die gegen Schweizerinnen und Schweizer im Ausland ergangen sind, ins schweizerische Strafregister eingetragen.
Unter dem Titel "Entfernung des Eintrags" werden in <ref-law> Fristen festgelegt, nach deren Ablauf Einträge aus dem Strafregister zu entfernen sind. Urteile, die eine Freiheitsstrafe von mindestens einem und weniger als fünf Jahren enthalten, werden von Amtes wegen entfernt, wenn über die gerichtlich zugemessene Strafdauer hinaus 15 Jahre verstrichen sind (<ref-law>). Nach der Entfernung darf die Eintragung nicht mehr rekonstruierbar sein. Das entfernte Urteil darf dem Betroffenen nicht mehr entgegengehalten werden (<ref-law>).
Aus dem gesetzgeberischen Willen der vollständigen Rehabilitation ist zu folgern, dass entfernte Urteile weder bei der Strafzumessung noch bei der Prognosebeurteilung zulasten der betroffenen Person berücksichtigt werden dürfen. Nach Ablauf der Entfernungsfrist sind die Rehabilitierungs- und Resozialisierungsinteressen der betroffenen Person mithin von Gesetzes wegen stärker zu gewichten als die öffentlichen Informations- und Strafbedürfnisse (<ref-ruling> E. 2.5 mit Hinweisen).
1.3 Der Beschwerdeführer wurde, wie im angefochtenen Urteil ausgeführt, mit Urteil des Landesgerichts Kleve vom 11. September 1992 zu einer Gefängnisstrafe von zwei Jahren und acht Monaten verurteilt. Diese Verurteilung wurde ins schweizerische Strafregister eingetragen. Gestützt auf <ref-law> wird dieser Eintrag von Amtes wegen entfernt, wenn über die gerichtlich zugemessene Strafdauer von zwei Jahren und acht Monaten hinaus 15 Jahre verstrichen sind. Die Entfernung erfolgt damit frühestens 17 Jahre und acht Monate nach dem Urteilsdatum vom 11. September 1992, das heisst jedenfalls nicht vor dem 12. Mai 2010 (vgl. insoweit aber auch <ref-law>). Dass das Urteil nicht, wie vom Beschwerdeführer behauptet, bereits am 12. September 2007 entfernt wurde, ergibt sich im Übrigen auch aus dem sich in den Akten befindlichen Strafregisterauszug vom 11. Januar 2008 (vorinstanzliche Akten act. A45).
2. 2.1 Der Beschwerdeführer rügt, die Vorinstanz hätte die Verfahrensverzögerung stärker strafreduzierend berücksichtigen müssen (Beschwerde S. 4).
2.2 Das in <ref-law> festgeschriebene Beschleunigungsgebot verpflichtet die Behörden, das Strafverfahren voranzutreiben, um die beschuldigte Person nicht unnötig über die gegen sie erhobenen Vorwürfe im Ungewissen zu lassen. Wird eine Verletzung des Beschleunigungsgebotes festgestellt, ist diesem Umstand angemessen Rechnung zu tragen.
2.3 Das Bundesgericht erwog mit Urteil 6B_794/2008 vom 1. Dezember 2008, die Vorinstanz habe der Verfahrensverzögerung für das sich über ein Jahr lang hinziehende Wiedereinsetzungsverfahren (von Februar 2004 bis Mai 2005) mit einer Strafreduktion von drei Monaten ausreichend Rechnung getragen. Eine weitere Verzögerung des vorinstanzlichen Verfahrens sei demgegenüber nicht erkennbar, und eine zusätzliche Reduktion der Strafe falle daher unter dem Gesichtspunkt einer Verletzung des Beschleunigungsgebots ausser Betracht (E. 3.2).
Auch zwischen dem Erlass des Urteils des Bundesgerichts vom 1. Dezember 2008 und dem Erlass des angefochtenen Urteils ist der Vorinstanz keine Verfahrensverzögerung anzulasten. Vielmehr hat sie den Verfahrensbeteiligten umgehend Gelegenheit zur Stellungnahme eingeräumt und im Anschluss an den Schriftenwechsel rasch entschieden.
Die Vorinstanz verletzt kein Bundesrecht, indem sie die Strafe nicht noch zusätzlich herabsetzt.
3. 3.1 Der Beschwerdeführer wendet sich gegen die Verweigerung des teilbedingten Strafvollzugs und hebt hervor, er habe sich nunmehr seit über acht Jahren wohl verhalten. Indem die Vorinstanz es versäumt habe, seinen positiven Lebenswandel bis zum Urteilszeitpunkt miteinzubeziehen, habe sie jedenfalls die ihr obliegende Begründungspflicht und damit Bundesrecht verletzt (Beschwerde S. 4 - 6).
Die Vorinstanz erwägt, der Beschwerdeführer habe seine deliktische Tätigkeit von November 1994 bis Mai 2001 unbekümmert um die beiden einschlägigen Verurteilungen in Deutschland 1992 und 1994 mit ungebremster Intensität weitergeführt. Seine darin zum Ausdruck gebrachte Unbelehrbarkeit sowie die enorme kriminelle Energie würden es verbieten, von besonders günstigen Umständen zu sprechen. Im Übrigen habe der Beschwerdeführer zwar seit seiner Entlassung aus dem vorzeitigen Strafvollzug im Mai 2003 keine Delikte mehr begangen. Eine solch positive Entwicklung dürfe indessen von einem Straftäter grundsätzlich erwartet werden und stelle keinen besonders günstigen Umstand im Sinne von <ref-law> dar. Dementsprechend komme ein teilbedingter Vollzug der Freiheitsstrafe nach <ref-law> nicht in Betracht (angefochtenes Urteil S. 25 f.).
3.2 Gemäss <ref-law> kann das Gericht den Vollzug einer Freiheitsstrafe von mindestens einem Jahr und höchstens drei Jahren nur teilweise aufschieben, wenn dies notwendig ist, um dem Verschulden des Täters genügend Rechnung zu tragen (<ref-law>).
Aus dem Sinn und Zweck von <ref-law> ergibt sich, dass die subjektiven Voraussetzungen von <ref-law> auch für die Anwendung von <ref-law> gelten (vgl. <ref-ruling> E. 5.3.1 mit Hinweisen). Wurde der Täter innerhalb der letzten fünf Jahre vor der Tat zu einer Freiheitsstrafe von mindestens sechs Monaten oder einer Geldstrafe von mindestens 180 Tagessätzen verurteilt, so ist gemäss <ref-law> der Aufschub nur zulässig, wenn besonders günstige Umstände vorliegen. Dies gilt auch bei Vorstrafen, die in ausländischen Urteilen ausgefällt worden sind, wenn sie bezüglich Strafwürdigkeit des Verhaltens, Mass der verhängten Strafe und Verfahrensgerechtigkeit den Grundsätzen des schweizerischen Rechts entsprechen (Urteil des Bundesgerichts 6B_540/2007 vom 16. Mai 2007 E. 4.1).
Unter den "besonders günstigen Umständen" sind solche Umstände zu verstehen, die ausschliessen, dass die Vortat die Prognose verschlechtert. Der früheren Verurteilung kommt damit zunächst die Bedeutung eines Indizes für die Befürchtung zu, dass der Täter weitere Straftaten begehen könnte. Die Gewährung des bedingten bzw. teilbedingten Strafvollzuges ist daher nur möglich, wenn eine Gesamtwürdigung aller massgebenden Faktoren den Schluss zulässt, dass trotz der Vortat eine begründete Aussicht auf Bewährung besteht. Dabei ist zu prüfen, ob die indizielle Befürchtung durch die besonders günstigen Umstände zumindest kompensiert wird. Das trifft etwa zu, wenn die neuerliche Straftat mit der früheren Verurteilung in keinerlei Zusammenhang steht, oder bei einer besonders positiven Veränderung in den Lebensumständen des Täters (<ref-ruling> E. 4.2.3).
3.3 Das deliktische Handeln des Beschwerdeführers, weswegen er im vorliegenden Verfahren zur Rechenschaft gezogen wird, setzte im November 1994 ein. Der Beschwerdeführer wurde weniger als fünf Jahre zuvor, nämlich 1992 und 1994, zu Freiheitsstrafen von mehr als sechs Monaten verurteilt, weshalb gestützt auf Art. 42 Abs. 2 i.V.m. <ref-law> besonders günstige Umstände vorliegen müssten, damit ein teilweiser Aufschub der Strafe zulässig wäre (vgl. auch Urteile des Bundesgerichts 6B_540/2007 vom 16. Mai 2007 E. 5.2 und 6B_393/ 2007 vom 2. November 2007 E. 4).
Dies ist nicht der Fall. In Würdigung der gesamten Umstände ist insbesondere der im angefochtenen Urteil gezogene Schluss auf die Unbelehrbarkeit und die ungemein erhebliche kriminelle Energie des Beschwerdeführers nicht zu beanstanden. Wie die Vorinstanz des Weiteren zutreffend betont hat, kann der Beschwerdeführer aus der Tatsache, dass er sich seit seiner Entlassung aus dem vorzeitigen Strafvollzug im Mai 2003 wohl verhalten hat, insoweit nichts Entscheidendes zu seinen Gunsten ableiten, darf doch eine solch positive Entwicklung von einem Straftäter grundsätzlich erwartet werden (vgl. Urteile des Bundesgerichts 6B_540/2007 vom 16. Mai 2008 E. 4.2.2 und 6B_67/2009 vom 30. April 2009 E. 1.2.3).
Die Vorinstanz verstösst nicht gegen <ref-law>, indem sie die ausgefällte Freiheitsstrafe von drei Jahren für vollziehbar erklärt. Ebenso wenig liegt eine Verletzung der Begründungspflicht gemäss <ref-law> vor, begründet die Vorinstanz doch eingehend, weshalb sie das Vorliegen besonders günstiger Umstände verneint.
4. Die Beschwerde ist abzuweisen. Bei diesem Ausgang des Verfahrens sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell Ausserrhoden, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 5. November 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Stohner