Sachverhalt:
A. M._ amtete seit der Gründung der X._ AG im Jahr 1993 bis Dezember 2007 als einziges Mitglied des Verwaltungsrats mit Einzelunterschrift. Vom 11. April 2006 bis 22. Februar 2008 war K._ als Geschäftsführer im Handelsregister eingetragen. Am xx. xx. 2008 wurde die Gesellschaft gestützt auf die Verfügung des Kantonsgerichts Schaffhausen vom xx. xx. 2008 wegen fehlenden Organen aufgelöst. Am 9. September 2008 wurde über das Vermögen der Gesellschaft der Konkurs eröffnet und am 5. Dezember 2008 mangels Aktiven wieder eingestellt. Mit Verfügung vom 12. Januar 2010 verpflichtete die Ausgleichskasse M._ zur Bezahlung von Schadenersatz für entgangene bundes- und kantonalrechtliche Sozialversicherungsbeiträge in der Höhe von Fr. 34'661.20 (einschliesslich FAK-Beiträge, Verwaltungskosten, Verzugszinsen, Mahngebühren und Betreibungskosten). Die hiegegen von M._ erhobene Einsprache wies die Ausgleichskasse mit Entscheid vom 25. Juni 2010 ab.
B. Die gegen den Einspracheentscheid erhobene Beschwerde wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 22. Juni 2012 ab, nachdem es vom Bundesamt für Sozialversicherungen (BSV) eine Stellungnahme vom 20. April 2011 zur Beitragspflicht der Arbeitnehmer der konkursiten Gesellschaft eingeholt hatte, in welcher auf die Bestätigung einer Sondervereinbarung der Deutschen Verbindungsstelle Krankenversicherung - Ausland (DVKA) vom 11. April 2011 verwiesen wurde.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt M._ beantragen, der vorinstanzliche Entscheid sei aufzuheben und er sei von der Schadenersatzpflicht zu befreien. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das kantonale Sozialversicherungsgericht und die Ausgleichskasse schliessen auf Abweisung der Beschwerde, während das BSV auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Die Zuständigkeit der II. sozialrechtlichen Abteilung des Bundesgerichts zum Entscheid über die streitige Schadenersatzpflicht erstreckt sich auch auf die Forderung für entgangene Sozialversicherungsbeiträge nach kantonalem Recht (Urteil 9C_704/2007 vom 17. März 2008 E. 1, nicht publ. in: <ref-ruling>, aber in: SVR 2008 FL Nr. 1 S. 1, 9C_720/2008 vom 7. Dezember 2009, E. 1). Diesbezüglich gilt eine qualifizierte Rügepflicht (Urteil 9C_684/2012 vom 7. März 2013 mit weiteren Hinweisen), welcher in der Beschwerde nicht nachgekommen wird. Insoweit ist darauf nicht einzutreten.
2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Eine unvollständige Sachverhaltsfeststellung stellt eine vom Bundesgericht ebenfalls zu korrigierende Rechtsverletzung im Sinne von <ref-law> dar (SEILER/VON WERDT/GÜNGERICH, Kommentar zum Bundesgerichtsgesetz, Bern 2007 N 24 zu Art. 97).
3. Die Vorinstanz hat die Bestimmungen über die Arbeitgeberhaftung (<ref-law>; <ref-law> in Verbindung mit <ref-law>) sowie die hiezu ergangene Rechtsprechung, insbesondere über den Eintritt des Schadens und über den Zeitpunkt der Kenntnis des Schadens (<ref-ruling>, 128 V 10, 119 V 89 E. 3 S. 92), die subsidiäre Haftung der Organe eines Arbeitgebers (<ref-ruling>, 126 V 237, 123 V 12 E. 5b S. 15, je mit Hinweisen), den zu ersetzenden Schaden (<ref-ruling> E. 3a S. 444, 123 V 12 E. 5b S. 15, je mit Hinweisen), die erforderliche Widerrechtlichkeit (<ref-ruling> E. 2a S. 195 mit Hinweisen), die Voraussetzung des qualifizierten Verschuldens und den dabei zu berücksichtigenden - differenzierten - Sorgfaltsmassstab zutreffend wiedergegeben (<ref-ruling> E. 3a S. 202, ZAK 1992 S. 248 E. 4b, je mit Hinweisen; vgl. auch THOMAS NUSSBAUMER, Die Haftung des Verwaltungsrates nach <ref-law>, in: AJP 9/96, S. 1081). Darauf wird verwiesen.
4. In Frage steht die Schadenersatzpflicht des Beschwerdeführers. Dabei ist zunächst streitig, ob die ausstehenden Beiträge, auf denen die Schadenersatzforderung gründet, zu Recht erhoben wurden.
4.1 Nach der Rechtsprechung findet im Schadenersatzprozess gemäss <ref-law> eine Überprüfung der den Ausständen zu Grunde liegenden Beitragsforderungen nicht mehr statt, soweit sie auf einer Nachzahlungs- oder Veranlagungsverfügung beruhen, die unangefochten in Rechtskraft erwachsen ist (Urteil 9C_684/2012 vom 7. März 2012 E. 7.1 mit Hinweisen). Durch die Möglichkeit der Gesellschaft sowie des betroffenen Arbeitnehmers, gegen eine Nachzahlungsverfügung Beschwerde zu führen, ist genügend Gewähr dafür geboten, dass die Organe der zahlungsunfähig gewordenen Arbeitgeberin nicht mit ungerechtfertigten Schadenersatzforderungen belastet werden. Deswegen haben sich die Organe im Schadenersatzverfahren eine vor der Konkurseröffnung eröffnete Nachzahlungsverfügung (vgl. AHI 1993 S. 173 E. 3b) entgegenhalten zu lassen. Eine Ausnahme gilt dann, wenn die Nachzahlungsverfügung der juristischen Person in einem Zeitpunkt eröffnet wurde, in welchem die ins Recht Gefassten als Organ ausgeschieden waren (<ref-ruling> E. 5). Ebenfalls vorbehalten bleiben jene Fälle, in denen sich aus den Akten Anhaltspunkte für eine zweifellose Unrichtigkeit der durch die Nachzahlungsverfügung festgesetzten Beiträge ergeben (AHI 1993 S. 172 E. 3a; ZAK 1991 S. 125 E. II/1b, Urteil H 77/03 vom 18. Januar 2005 E. 7).
4.2 Die Vorinstanz hat ausser Acht gelassen, dass der Beschwerdeführer nicht bis zur Konkurseröffnung über die Gesellschaft am 9. September 2008 als Verwaltungsrat amtete, sondern bereits im Dezember 2007 aus der Gesellschaft ausschied. Mithin war er im Zeitpunkt des Erlasses der beiden Nachzahlungsverfügungen vom 7. August 2008 nicht mehr Organ der Gesellschaft. Nach dem Gesagten sind die mit den Nachzahlungsverfügungen festgesetzten Beiträge deshalb zu überprüfen.
4.3 Es beruhen indes nicht alle der Schadenersatzforderung zu Grunde liegenden Beiträge auf Nachzahlungsverfügungen. Die Vorinstanz stellte zwar fest, allein ein Teil der Beitragsausstände beruhe auf rechtskräftigen Nachzahlungsverfügungen, weshalb die Beitragspflicht der Arbeitnehmer der X._ AG zu klären sei. Sie legte aber weder näher dar, welche Beiträge für welche Arbeitnehmer und welche Periode auf einer Nachzahlungsverfügung beruhten, noch machte sie weitergehende Feststellungen im Zusammenhang mit der Höhe der Schadenersatzforderung.
4.4 Mit Nachzahlungsverfügungen vom 7. August 2008 festgesetzt wurden die nicht abgerechneten Beiträge gemäss der Arbeitgeberkontrolle vom 10. Juli 2008 für das Jahr 2006 von Fr. 2'104.40 (betreffend L._ für September bis Dezember mit einem Lohn von Fr. 10'822.- und P._ für Dezember mit Fr. 4'100.-) sowie für das Jahr 2007 von Fr. 2'890.20 (betreffend L._, für Januar bis März mit einem Lohn von Fr. 18'480.- und U._ für Januar bis März mit Fr. 1'272.-) zuzüglich Verzugszinsen von Fr. 168.65 und Fr. 87.10 sowie Mahngebühren von Fr. 30.-, insgesamt Fr. 5'280.35.
4.5 Die übrigen ausstehenden Beiträge von Fr. 29'380.85 betreffen die mit den Lohnbescheinigungen deklarierten Löhne 2006 und 2007 und wurden wie folgt festgesetzt:
4.5.1 Ein erster Teil der Beiträge 2006 in der Höhe von Fr. 1'883.90 (betreffend E._ mit einem Lohn von Fr. 13'500.- für September bis November 2006, inklusive Mahn- und Betreibungskosten sowie Verzugszinsen) wurde gestützt auf die am 27. Februar 2007 bei der Ausgleichskasse eingegangene Lohnbescheinigung 2006 am 8. März 2007 in Rechnung gestellt, am 11. Mai 2007 gemahnt und am 15. August 2007 betrieben. Nachdem kein Rechtsvorschlag erhoben wurde, war die Ausgleichskasse nicht mehr gehalten, das Veranlagungsverfahren durchzuführen (Rz. 2160 der Weisung des Bundesamtes für Sozialversicherungen über den Bezug der Beiträge, WBB; ZAK 1978 S. 300; Urteil H 420/99 E. 3b mit Hinweis auf das Urteil H 63/98 vom 15. Dezember 1998) und konnte die Betreibung direkt fortsetzen, was zu einem definitiven Pfändungsverlustschein vom 18. Januar 2008 führte. Eine Überprüfung der Beitragsforderung findet vorliegend deshalb nicht mehr statt. Eine zweifellose Unrichtigkeit ist nicht gegeben (vgl. E. 5.2 und 5.3 nachfolgend).
4.5.2 Nach Einreichung einer ergänzten Lohnbescheinigung 2006 sowie der Lohnbescheinigung 2007 im September 2007 stellte die Ausgleichskasse am 8. Oktober 2007 die restlichen Beiträge für 2006 in der Höhe von Fr. 6'701.25 und am 12. Oktober 2007 für 2007 in der Höhe von Fr. 20'276.55 in Rechnung. Dies betraf folgende Arbeitnehmer und Abrechnungsmonate:
für 2006:
C._ Dezember Fr. 5'600.-
I._ Dezember Fr. 4'400.-
G._ Dezember Fr. 4'400.-
Y._ Dezember Fr. 4'100.-
S._ Dezember Fr. 4'240.-
B._ Dezember Fr. 5'500.-
A._ Dezember Fr. 6'035.-
R._ Dezember Fr. 5'770.-
U._ Dezember Fr. 5'500.-
E._ September bis November Fr. 13'500.-
für 2007:
C._ Januar bis März Fr. 16'800.-
I._ Januar bis März Fr. 13'200.-
G._ Januar bis März Fr. 13'200.-
Y._ Januar bis März Fr. 12'300.-
S._ Januar bis März Fr. 12'720.-
B._ Januar bis März Fr. 16'500.-
A._ Januar bis März Fr. 18'105.-
R._ Januar bis März Fr. 17'310.-
U._ Januar bis März Fr. 18'500.-
H._ Januar Fr. 4'500.-
Beide Rechnungen wurden am 5. Dezember 2007 gemahnt und am 21. Februar 2008 betrieben, wobei die Zahlungsbefehle im Rahmen eines Rechtshilfegesuches an die Adresse von K._ in Deutschland zugestellt wurden und darauf kein Rechtsvorschlag erhoben wurde. Die Betreibung überschnitt sich mit der Verfügung des Kantonsgerichts Schaffhausen vom 19. Februar 2008, mit welcher die Gesellschaft wegen fehlenden Organen von Amtes wegen nach Art. 154 HregV aufgelöst wurde. Schliesslich wurde mit Verfügung vom 8. August 2008 das Fortsetzungsbegehren der Ausgleichskasse vom Betreibungs- und Konkursamt Schaffhausen zurückgewiesen.
Der Beschwerdeführer war indes bereits im Dezember 2007 als Organ der Gesellschaft ausgeschieden. Deshalb sind auch diese Beitragsforderungen zu überprüfen und es erübrigen sich Weiterungen zur besonderen Sachlage eines Veranlagungsverfahrens bei Auflösung der Gesellschaft mangels Organen und gleichzeitiger Betreibung.
4.6 Mit Ausnahme der sich aus dem an E._ ausbezahlten Lohn ergebenden Beiträge sind damit sämtliche Beitragsforderungen zu prüfen.
5. Streitig sind die Beitragsforderungen nicht in masslicher Hinsicht, sondern mit Blick auf die Unterstellung der betreffenden Mitarbeiter unter die Schweizerischen Rechtsvorschriften.
Der Beschwerdeführer bringt vor, die von der X._ AG beschäftigten Arbeitnehmer unterstünden nicht der Beitragspflicht, da sie ihren Wohnsitz in Deutschland gehabt hätten und nicht in der Schweiz tätig gewesen seien. Mit der nachträglichen Unterstellung unter die Schweizerischen Rechtsvorschriften sei er nicht einverstanden.
Demgegenüber hat die Vorinstanz zur Begründung der Beitragspflicht mit der Ausgleichskasse auf die Sondervereinbarung des BSV mit der DVKA verwiesen (Bestätigung der DVKA vom 11. April 2011) und festgestellt, damit seien die Arbeitnehmer der X._ AG für den Zeitraum Dezember (recte: September) 2006 bis November 2007 den schweizerischen Rechtsvorschriften unterstellt worden, weshalb von der Beitragspflicht der X._ AG auszugehen sei.
Demgegenüber hat die Vorinstanz zur Begründung der Beitragspflicht mit der Ausgleichskasse auf die Sondervereinbarung des BSV mit der DVKA verwiesen (Bestätigung der DVKA vom 11. April 2011) und festgestellt, damit seien die Arbeitnehmer der X._ AG für den Zeitraum Dezember (recte: September) 2006 bis November 2007 den schweizerischen Rechtsvorschriften unterstellt worden, weshalb von der Beitragspflicht der X._ AG auszugehen sei.
5.1 5.1.1 Gemäss <ref-law> sind natürliche Personen mit Wohnsitz in der Schweiz (lit. a) und natürliche Personen, die in der Schweiz einer Erwerbstätigkeit ausüben (lit. b), in der AHV obligatorisch versichert.
5.1.2 In einem grenzüberschreitenden Sachverhalt ist zudem das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedern andererseits über die Freizügigkeit (FZA; SR 0.142.112.681) zu beachten. Nach Art. 1 Abs. 1 des auf der Grundlage des Art. 8 des FZA ausgearbeiteten und Bestandteil des Abkommens bildenden (Art. 15 FZA) Anhangs II ("Koordinierung der Systeme der sozialen Sicherheit") FZA in Verbindung mit Abschnitt A dieses Anhangs wenden die Vertragsparteien untereinander insbesondere die Verordnung (EG) Nr. 883/2004 des Europäischen Parlaments und des Rates vom 29. April 2004 zur Koordinierung der Systeme der sozialen Sicherheit (SR 0.831.109.268.1; kurz: VO 883/2004) und die Verordnung (EG) Nr. 987/2009 des Europäischen Parlaments und des Rates vom 16. September 2009 zur Festlegung der Modalitäten für die Durchführung der VO 883/2004 (SR 0.831.109.268.11) oder gleichwertige Vorschriften an.
Die beiden genannten gemeinschaftsrechtlichen Verordnungen sind für die Schweiz durch den Beschluss Nr. 1/2012 des Gemischten Ausschusses vom 31. März 2012 zur Ersetzung des Anhangs II des Abkommens über die Koordinierung der Systeme der sozialen Sicherheit per 1. April 2012 in Kraft getreten (AS 2012 2345; vgl. auch Urteil 8C_455/2011 vom 4. Mai 2012 E. 2.1).
Die VO 883/2004, welche die Verordnung (EWG) Nr. 1408/71 des Rates vom 14. Juni 1971 zur Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbstständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (SR 0.831.109.268.1; kurz: VO Nr. 1408/71) ersetzt hat, begründet gemäss ihren Übergangsbestimmungen jedoch keinen Anspruch für den Zeitraum vor dem Beginn ihrer Anwendung (Art. 87 Abs. 1), weshalb vorliegend noch die VO 1408/71 und die Verordnung (EWG) Nr. 574/72 des Rates vom 21. März 1972 über die Durchführung der VO (EWG) Nr. 1408/71 über die Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbstständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (kurz: VO 574/72; SR 0.831.109.268.11) anwendbar bleibt (vgl. Urteil 8C_385/2012 E. 4.2 zur Publikation vorgesehen; vgl. auch <ref-ruling> E. 4.1.3 S. 396 und Urteil 8C_670/2012 E. 3.1).
5.1.3 Die VO Nr. 1408/71 gilt unter anderem auch für Rechtsvorschriften über Zweige der sozialen Sicherheit, die Leistungen bei Alter und an Hinterbliebene betreffen (Art. 4 Abs. 1 lit. c und d). Die entsprechenden Bestimmungen finden in der Alters- und Hinterlassenenversicherung durch den Verweis in <ref-law> Anwendung.
5.1.4 Titel II der Verordnung Nr. 1408/71 (Art. 13 bis 17a) enthält allgemeine Kollisionsregeln zur Bestimmung der anzuwendenden Rechtsvorschriften. Dabei legt Art. 13 Abs. 1 den kollisionsrechtlichen Grundsatz der Einheitlichkeit der anwendbaren Rechtsvorschriften nach den Regeln gemäss Art. 13 Abs. 2 bis Art. 17a in dem Sinne fest, dass für jede betroffene Person die Rechtsvorschriften nur eines Mitgliedstaates massgebend sind (<ref-ruling> E. 3.1 S. 537 und 258 E. 4.2 S. 263 f. mit Hinweis). Ausnahmen vorbehalten, gilt für Arbeitnehmende das Beschäftigungslandprinzip. Dies trifft auch dann zu, wenn sie im Gebiet eines anderen Mitgliedstaates wohnen oder ihr Arbeitgeber oder das Unternehmen, das sie beschäftigt, den Wohn- oder Betriebssitz im Gebiet eines anderen Mitgliedstaates hat (Grundsatz der lex loci laboris; Art. 13 Abs. 2 lit. a der Verordnung Nr. 1408/71; <ref-ruling> E. 3.1 S. 537 und 258 E.4.2 S. 263 f. mit Hinweis). Eine Ausnahme ist unter anderem vorgesehen für eine Person, die in mehreren Mitgliedstaaten abhängig beschäftigt oder selbstständig tätig ist. Handelt es sich hierbei um eine Person, die nicht als Mitglied des fahrenden oder fliegenden Personals eines Unternehmens beschäftigt ist, unterliegt sie den Rechtsvorschriften des Mitgliedstaates, in dessen Gebiet sie wohnt, wenn sie ihre Tätigkeit zum Teil im Gebiet dieses Staates ausübt oder wenn sie für mehrere Unternehmen oder mehrere Arbeitgeber tätig ist, die ihren Sitz oder Wohnsitz im Gebiet verschiedener Mitgliedstaaten haben (Art. 14 Abs. 2 lit. b/i). Sodann unterliegt sie den Rechtsvorschriften des Mitgliedstaates, in dessen Gebiet das Unternehmen oder der Arbeitgeber, das bzw. der sie beschäftigt, seinen Sitz oder Wohnsitz hat, sofern sie nicht im Gebiet eines Mitgliedstaates wohnt, in denen sie ihre Tätigkeiten ausübt (Art. 14 Abs. 2 lit. b/ii, vgl. <ref-ruling> E. 3).
5.1.5 Gemäss Art. 17 der VO 1408/71 können zwei oder mehrere Mitgliedstaaten, die zuständigen Behörden dieser Staaten oder die von diesen Behörden bezeichneten Stellen im Interesse bestimmter Personengruppen oder bestimmter Personen Ausnahmen von den Artikeln 13 bis 16 vereinbaren.
5.2 Das BSV beantragte nach entsprechenden Abklärungen der Ausgleichskasse im Zusammenhang mit der Auszahlung von Insolvenzentschädigungen sowie einem Strafverfahren wegen Zweckentfremdung von AHV-Beiträgen am 2. Februar 2011 bei der DVKA eine Sondervereinbarung betreffend die Beitragsunterstellung der Arbeinehmer der konkursiten Gesellschaft. Die DVKA begründete ihr Einverständnis mit einer Sondervereinbarung in ihrem Schreiben vom 11. April 2011 nicht. Wie sich jedoch dem Antragsschreiben des BSV entnehmen lässt, gingen die Ausgleichskasse und das BSV davon aus, die Mitarbeiter seien ausschliesslich in Deutschland tätig gewesen. Die Sondervereinbarung stellt damit eine Ausnahme von Art. 14 Abs. 2 lit. b/i der VO 1408/71 (Unterstellung unter die deutschen Rechtsvorschriften) dar (vgl. E. 5.1.4 hievor).
Entgegen der Auffassung des Beschwerdeführers sind solche Vereinbarungen auch rückwirkend zulässig. Nach der Rechtsprechung des EuGH haben die Mitgliedstaaten die Möglichkeit, die Anwendung der Rechtsvorschriften eines dieser Mitgliedstaaten auch mit rückwirkender Kraft zu beschliessen (EuGH, Rechtssache 101/83 (Brusse) Slg. 1984, 2223 ff. = SozR 6050 Art. 17 Nr. 2). Art. 17 der VO 1408/71 gewährt nach seinem Wortlaut den Mitgliedstaaten eine umfassende Vereinbarungsbefugnis, wenn es heisst, dass sie Ausnahmen von den Art. 13 bis 16 vereinbaren können. Art. 17 enthält weder Anhaltspunkte, aus denen auf ein Verbot von Vereinbarungen mit rückwirkender Kraft geschlossen werden könnte, noch hindert er, dass für einen längeren Zeitraum pauschal die Rechtsvorschriften eines der Mitgliedstaaten für anwendbar erklärt werden (Steinmeyer, in: Fuchs [Hrsg.], Europäisches Sozialrecht, 3. Aufl. 2005, Rz. 2 bis 4 zu Art. 13 VO 1408/71 S. 172 f.). Damit steht die Beitragspflicht der an von der Sondervereinbarung erfassten Arbeitnehmer ausbezahlten Löhne fest.
5.3 Die DVKA hat eine ausnahmsweise Nicht-Unterstellung unter die deutschen Rechtsvorschriften für folgende Arbeitnehmer bestätigt:
C._ Dez. '06 bis März '07
I._ Dez. '06 bis März '07
G._ Dez. '06 bis Sept. '07
Y._ Dez. '06 bis März '07 und Mai - Sept. '07
S._ Dez. '06 bis Dez. '06
B._ Dez. '06 bis Juli '07
A._ Dez. '06 bis März '07 und Juli - Nov. '07
R._ Dez. '06 bis März '07
U._ Dez. '06 bis März '07 und Juli - Nov. '07
E._ Sept. -Nov. '06
H._ Jan. '07 bis Jan. '07
L._ Sept. '06 bis März '07 und Juni - Okt. '07
Entgegen der Auffassung der Vorinstanz umfasst die Sondervereinbarung indes nicht alle Arbeitnehmer, für deren Löhne Beiträge erhoben und der Schadenersatzforderung zu Grunde gelegt wurden. Von der Vereinbarung nicht erfasst wird P._, für welche mit der Arbeitgeberkontrolle ein Lohn für den Monat Dezember 2006 von Fr. 4'100.- festgestellt wurde (vgl. E. 4.4). Weshalb diese Arbeitnehmerin von der Vereinbarung nicht erfasst wurde, lässt sich den Akten nicht entnehmen. Die Ausgleichskasse hat sich dazu auch nicht geäussert, obwohl der Nachweis, dass die Arbeitgebenden Beiträge schulden, die sie nicht bezahlt haben, ihr obliegt (vgl. Rz. 2137 WBB). Nachdem die anderen beiden mit der Arbeitgeberkontrolle erfassten Mitarbeiter L._ und U._ (vgl. E. 4.4 hievor) in der Vereinbarung aufgeführt werden, ist davon auszugehen, dass P._ beim Antrag an die DVKA absichtlich weggelassen oder von der DVKA nicht bestätigt wurde. Ihre Beitragspflicht ist mithin (auch in Anbetracht ihres mit der Arbeitgeberkontrolle festgestellten Wohnsitzes in Deutschland) nicht erstellt. Damit sind die auf P._ entfallenden, aufgerechneten Beiträge nicht geschuldet und betragen inklusive anteilsmässigem Verzugszins (Fr. 46.35) und Mahngebühren (Fr. 3.55) insgesamt Fr. 628.10 (10.1% AHV/IV/EO-Beitrag auf die Lohnsumme von Fr. 4'100.- = Fr. 414.10, 1.4% FAK von Fr. 4'100.- = Fr. 57.40, 2% ALV von Fr. 4'100.- = Fr. 82.-, Verwaltungskosten 3% auf die Beitragssumme von Fr. 414.10 = Fr. 12.40, Sozialfonds 0.3% = Fr. 12.30), weshalb die Schadenersatzforderung sich um diesen Betrag auf Fr. 34'033.10 reduziert.
6. 6.1 Damit steht fest, dass die konkursite Gesellschaft Beiträge im Umfange von Fr. 34'033.10 nicht bezahlt hat und daher den ihr als Arbeitgeberin obliegenden Pflichten gemäss <ref-law> in Verbindung mit <ref-law> nur unvollständig nachgekommen ist. Sie hat damit Vorschriften im Sinne von <ref-law> missachtet (vgl. statt vieler: <ref-ruling> E. 1 am Ende), was grundsätzlich die volle Schadenersatzpflicht gemäss <ref-law> nach sich zieht.
Zu prüfen bleibt, ob diese zum Beitragsverlust führende Pflichtverletzung des Arbeitgebers dem Beschwerdeführer - seines Zeichens einziger Verwaltungsrat und damit formelles Organ einer Aktiengesellschaft als juristischer Person (Art. 626 Ziff. 6 in Verbindung mit <ref-law>), welches grundsätzlich als Schadenersatzpflichtiger in Frage kommt - als grobfahrlässiges Verhalten anzurechnen ist.
6.2 Ob ein Organ schuldhaft gehandelt hat, hängt entscheidend von der Verantwortung und den Kompetenzen ab, die ihm von der juristischen Person übertragen wurden. Bei nicht geschäftsführenden Verwaltungsratsmitgliedern von Aktiengesellschaften ist entscheidend, ob sie den ihnen obliegenden Kontroll- und Aufsichtspflichten nachgekommen sind. Nach <ref-law> obliegt dem Verwaltungsrat die Oberaufsicht über die mit der Geschäftsführung betrauten Personen, namentlich im Hinblick auf die Befolgung der Gesetze, Statuten, Reglemente und Weisungen. Gemäss dieser Bestimmung hat das Verwaltungsratsmitglied nicht nur die Pflicht, an den Verwaltungsratssitzungen teilzunehmen, sondern sich periodisch über den Geschäftsgang zu informieren und bei Unregelmässigkeiten in der Geschäftsführung einzuschreiten (vgl. FORSTMOSER/MEIER-HAYOZ/NOBEL, Schweizerisches Aktienrecht, § 30, N. 49). Die Bestimmung entspricht weitgehend dem bis Ende Juni 1992 gültig gewesenen <ref-law>, wonach die Verwaltung einer Aktiengesellschaft die mit der Geschäftsführung beauftragten Personen zu überwachen und sich regelmässig über den Geschäftsgang unterrichten zu lassen hatte. Wie das Eidgenössische Versicherungsgericht hiezu festgestellt hat, setzt die Sorgfaltspflicht voraus, dass der Verwaltungsrat die ihm unterbreiteten Berichte kritisch liest, nötigenfalls ergänzende Auskünfte verlangt und bei Irrtümern oder Unregelmässigkeiten einschreitet. Dabei wird es aber einem Verwaltungsratspräsidenten einer Grossfirma nicht als grobfahrlässiges Verschulden angerechnet werden können, wenn er nicht jedes einzelne Geschäft, sondern nur die Tätigkeit der Geschäftsleitung und den Geschäftsgang im Allgemeinen überprüft und daher beispielsweise nicht beachtet, dass in Einzelfällen die Abrechnung der Lohnbeiträge nicht erfolgt ist. Das Gegenstück wäre der Präsident des Verwaltungsrates einer Firma, der faktisch das einzige ausführende Organ der Firma ist, oder aber der Verwaltungsratspräsident einer Firma, dem bekannt ist oder doch nach den jeweiligen Umständen bekannt sein sollte, dass die Abrechnungspflicht möglicherweise mangelhaft erfüllt wird (<ref-ruling> E. 4a S. 223; <ref-ruling> E. 3a S. 202; ZAK 1985 S. 620 E. 3b, Urteil H 182/06 vom 29. Januar 2008, je mit Hinweisen). Zwar können einzelne Geschäftsführungsfunktionen delegiert werden. Zur Wahrung der geforderten Sorgfalt gehört jedoch neben der richtigen Auswahl des geeigneten Mandatsträgers auch dessen Instruktion und Überwachung. So kann sich der Geschäftsführer allein durch Delegation der Aufgaben nicht seiner Verantwortung entledigen. Dies gilt für einen Vereinspräsidenten (AHI 2002 S. 51, H 200/01) ebenso wie für einen Verwaltungsrat (<ref-ruling> E. 5b), einen geschäftsführenden Gesellschafter einer GmbH (AHI 2000 S. 220) oder einen Stiftungsrat (Urteil H 14/00 vom 30. Juli 2001).
6.3 Das kantonale Gericht hat das Verhalten des Beschwerdeführers als grobfahrlässig beurteilt und den Kausalzusammenhang mit dem eingetretenen Schaden bejaht. Daran ändere nichts, dass die ausstehenden Beitragszahlungen ausschliesslich aus den Geschäftsjahren 2006 und 2007 resultierten, in welchen K._ Geschäftsführer gewesen sei und 10 Mitarbeiter eingestellt habe, während die Firma vorher kein Personal beschäftigt habe. Der Beschwerdeführer habe angesichts der Umstände nicht darauf vertrauen dürfen, dass die X._ AG weiterhin inaktiv bleiben würde. Vielmehr habe er mit der Aufnahme einer geschäftlichen Tätigkeit rechnen müssen, zumal er selbst für die Führung der Buchhaltung zuständig gewesen sei, welche durch Mitarbeiter seiner Unternehmung geführt worden sei. Er habe jedenfalls die Geschäftstätigkeit der X._ AG, namentlich des Beitragswesens, ungenügend überwacht.
Das Bundesgericht beurteilt die Haftungsfrage nicht abweichend. Es kann in erster Linie auf die diesbezüglichen Erwägungen des angefochtenen Entscheids verwiesen werden.
6.4 Soweit der Beschwerdeführer grundsätzliche Kritik an der Organhaftung nach <ref-law> übt, geht diese fehl: Das Bundesgericht hat bereits wiederholt zur Kritik an der Rechtsprechung zur Arbeitgeber-Organhaftung Stellung bezogen; unter Verweis auf <ref-ruling>, 114 V 219 sowie Urteil H 112/03 vom 2. November 2004 erübrigen sich dazu Weiterungen.
6.5 Sodann widerspricht sich der Beschwerdeführer selbst, wenn er anführt, die X._ AG sei ohne Ausnahme inaktiv gewesen, nachdem er selbst die Lohnbescheinigungen eingereicht hat (auf dem Begleitschreiben vom 24. September 2007 befindet sich seine Unterschrift) und dabei weder einen Vorbehalt zur Beitragsunterstellung im Zusammenhang mit einer zusätzlichen ausländischen Tätigkeit der Mitarbeiter noch bezüglich allfälliger nicht ausbezahlter Löhne angebracht hat. Davon, dass sein Fehlverhalten eindeutig in den Hintergrund tritt, kann unter diesen Umständen nicht die Rede sein. Mit der Vorinstanz ist festzuhalten, dass es unglaubwürdig ist, wenn der Beschwerdeführer erneut anführt, K._ habe als Direktor der Gesellschaft ohne sein Wissen und eigenmächtig Arbeitnehmer angestellt und die Lohnzahlungen bar ausgerichtet, ohne dass er etwas davon gewusst habe. Im Übrigen hat der Beschwerdeführer selbst auch das Bestellformular für einen Versicherungsausweis eines Mitarbeiters eingereicht. Es ist ihm vorzuwerfen, dass er die ihm obliegenden Überwachungspflichten (vgl. E. 6.2) nicht wahrgenommen hat, insbesondere bei solch überschaubaren Verhältnissen.
6.6 An seinem Verschulden ändert entgegen der Auffassung des Beschwerdeführers schliesslich auch nichts, dass die Beitragspflicht mit der Sondervereinbarung gemäss Art. 17 VO1408/71 erst rückwirkend festgestellt wurde und er vom genauen Hintergrund dieser Unterstellung erst anlässlich der Aktenkonsultation im Hinblick auf die Anfechtung des nunmehr angefochtenen Entscheides der Vorinstanz vom 22. Juni 2012 erfuhr. Soweit er geltend machen will, er habe von der Beitragspflicht vorher gar nicht wissen können, weshalb ihm auch keine Pflichtverletzung vorgeworfen werden könne, trifft es zwar zu, dass nach der Rechtsprechung der Vorwurf schuldhafter Schadensverursachung dann entfallen kann, wenn sich über die beitragsrechtliche Qualifikation der fraglichen Entgelte in guten Treuen streiten lässt, wobei damit nicht von vornherein die Pflicht zu Rückstellungen entfällt (SVR AHV Nr. 9 S. 25, H 8/07 E. 7).
Hier ist insbesondere zu berücksichtigen, dass der Beschwerdeführer selbst, wie bereits erwähnt, im Jahre 2007 die Lohnbescheinigungen für 2006 und 2007 eingereicht hat. Wenn er der Meinung gewesen wäre, die Mitarbeiter seien in der Schweiz nicht abrechnungspflichtig, hätte er bei der Einreichung der Lohnbescheinigung mindestens einen Vorbehalt hinsichtlich der Beitragsunterstellung anbringen können. Dergleichen ist aus den Akten nicht ersichtlich. Vielmehr wurden die Beiträge von den Lohnzahlungen tatsächlich abgezogen. Bei dieser Sachlage musste der Beschwerdeführer mit der Beitragserhebung rechnen und war deshalb verpflichtet, für verfügbare Rückstellungen zu sorgen, was er jedoch unterlassen hat.
6.7 Insoweit sich der Beschwerdeführer auf ein Mitverschulden der Ausgleichskasse beruft, weil ihn die - an die Firma adressierten - Mahnungen nicht erreicht hätten, so ist dies ausschliesslich ein (firmen-)internes Problem. Dass die Ausgleichskasse längere Zeit keine Inkassoschritte unternommen und den Vollzug des Zahlungsverkehrs nur unzureichend überwacht hat, stellt eine pauschale Behauptung dar, die nicht weiter untermauert ist. Im Gegenteil präsentiert sich die Vorgehensweise der Ausgleichskasse alles andere als schleppend (vgl. E. 4.5.1 und 4.5.2).
6.8 Zusammenfassend ist deshalb von einem haftungsbegründenden qualifizierten Verschulden des Beschwerdeführers auszugehen.
7. Angesichts des anteilsmässig geringen Obsiegens werden die Gerichtskosten vollumfänglich dem Beschwerdeführer auferlegt (<ref-law>); ebenso wenig ist eine Parteientschädigung geschuldet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, soweit darauf einzutreten ist. Die Verfügung der Ausgleichskasse des Kantons Schaffhausen vom 12. Januar 2010 und ihr Einspracheentscheid vom 25. Juni 2010 werden insoweit abgeändert, dass der Beschwerdeführer der Ausgleichskasse Schadenersatz in der Höhe von Fr. 34'033.10 zu zahlen hat.
2. Die Gerichtskosten von Fr. 3000.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Schaffhausen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 15. Mai 2013
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Die Gerichtsschreiberin: Helfenstein