Sachverhalt:
A. S._ ist der Ausgleichskasse des Kantons Graubünden als selbstständig erwerbender Patentanwalt angeschlossen. Nach Erlass provisorischer Verfügungen setzte die Ausgleichskasse jeweils mit Verfügungen vom 15. April 2004, 2./4. Mai 2006 und 12. Juli 2007 die für die Jahre 2002, 2003 und 2004 geschuldeten persönlichen AHV/IV/EO-Beiträge gestützt auf die entsprechenden Meldungen der Steuerverwaltung des Kantons Graubünden vom 30. Januar 2004, 13. Dezember 2005 sowie 7. Mai 2007 definitiv fest. Nachdem die Ausgleichskasse S._ am 14. November 2007 mitgeteilt hatte, es sei ihr bei der Verarbeitung der Steuermeldung betreffend die Beitragsverfügung 2004 ein Fehler unterlaufen - sie hätten nur das selbstständige Einkommen in der Schweiz verfügt und nicht das gesamte selbstständige Einkommen -, erliess sie am 22. November 2007 eine rektifizierte Nachtragsverfügung für 2004 (Einkommen aus selbstständiger Erwerbstätigkeit von Fr. 369'338.- statt Fr. 223'965.-) und am 20. Dezember 2007 zwei Nachtragsverfügungen für 2002 (Einkommen von Fr. 388'150.- statt Fr. 238'150.-) und für 2003 (Fr. 473'967.- statt Fr. 296'515.-). Die dagegen erhobene Einsprache wurde mit Einspracheentscheid vom 18. April 2008 erledigt, wobei das Dispositiv lautete: "Die Einsprache wird abgewiesen. In Bezug auf das Beitragsjahr 2002 ist die Einsprache gutzuheissen, soweit in Deutschland erzieltes Erwerbseinkommen mitberücksichtigt wurde, welches vom 1.1.2002 bis 31.5.2002 erzielt wurde".
B. Die hiegegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 16. September 2008 (Versand am 27. November 2008) ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt S._ beantragen, der vorinstanzliche Entscheid und die angefochtenen Verfügungen seien aufzuheben; eventualiter sei die angefochtene Beitragsverfügung für 2002 ersatzlos aufzuheben.
Die Ausgleichskasse und das Bundesamt für Sozialversicherungen (BSV) schliessen auf Abweisung der Beschwerde.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
2. Nicht bestritten ist, dass der Beschwerdeführer in der Schweiz Einkommen aus selbstständiger Erwerbstätigkeit erzielt und dafür ahv-abrechnungspflichtig ist. Streitig und zu prüfen ist hingegen, ob die Ausgleichskasse mit den rektifizierten Nachtragsverfügungen der Beitragsjahre 2002-2004 unter dem Titel der Wiedererwägung auch das in Deutschland erzielte Einkommen der Beitragspflicht unterstellen durfte.
2.1 Die Vorinstanz hat die Bestimmungen und Grundsätze über die Wiedererwägung formell rechtskräftiger Verfügungen (<ref-law>) und die dabei vorausgesetzte zweifellose Unrichtigkeit (<ref-ruling> E. 2c S. 469, vgl. auch SZS 2009 S. 401, E. 4.1, 9C_828/2008, und SVR 2008 IV Nr. 53 S. 177 E. 4.2, I 803/06) zutreffend dargelegt. Darauf wird verwiesen.
2.2 Nach dem klaren Wortlaut von <ref-law> in Verbindung mit <ref-law> ist eine Wiedererwägung generell im Sozialversicherungsrecht zulässig, mithin auch für AHV-Beiträge. Das entspricht der bereits vor dem Inkrafttreten des ATSG geltenden Rechtslage (<ref-ruling> E. 6 S. 5; Urteile H 97/03 vom 10. September 2003, E. 1.1; H 184/95 vom 4. Juli 1997, E. 5b; H 23/95 vom 30. August 1995, E. 6b; vgl. auch ZAK 1980 S. 496, H 134/77) und wurde auch unter der Herrschaft des ATSG von der Rechtsprechung so bestätigt (Urteil 9C_910/2007 vom 6. Juni 2008, E. 4; vgl. auch Forster, AHV-Beitragsrecht, 2007, S. 204f.). Die Vorbringen des Beschwerdeführers geben keinen Anlass, davon abzuweichen:
Die Auslegung des Gesetzes ist auf die Regelungsabsicht des Gesetzgebers und die von ihm erkennbar getroffenen Wertentscheidungen auszurichten. Ausgangspunkt der Auslegung einer Norm bildet ihr Wortlaut. Vom daraus abgeleiteten Sinne ist jedoch abzuweichen, wenn triftige Gründe dafür bestehen, dass der Gesetzgeber diesen nicht gewollt haben kann. Solche Gründe können sich insbesondere aus der Entstehungsgeschichte der Norm, aus ihrem Zweck oder aus dem Zusammenhang mit anderen Vorschriften ergeben. Insoweit wird vom historischen, teleologischen und systematischen Auslegungselement gesprochen. Bei der Auslegung einer Norm sind daher neben dem Wortlaut diese herkömmlichen Auslegungselemente zu berücksichtigen (<ref-ruling> E. 4 S. 277 mit Hinweisen).
Zwar mag es zutreffen, dass im Rahmen der parlamentarischen Beratung im Zusammenhang mit der Wiedererwägung hauptsächlich an die Leistungsseite gedacht wurde, doch ergeben sich aus der Entstehungsgeschichte keine Hinweise, dass entgegen dem klaren Wortlaut des Gesetzes die Wiedererwägung für Beiträge ausgeschlossen werden sollte. Auch dass die Voraussetzungen für eine Nachveranlagung im Steuerrecht strenger sind, gibt dazu keinen Anlass. Zwar ist das AHV-Beitragsrecht in mancher Beziehung mit dem Steuerrecht harmonisiert, doch ist eine harmonisierende Betrachtung dort nicht zulässig, wo die gesetzliche Regelung in der AHV vom Steuerrecht abweicht (<ref-ruling> E. 3.2 S. 253; <ref-ruling> E. 4.2 S. 107).
Zu Unrecht beruft sich der Beschwerdeführer auf das Legalitätsprinzip im Abgaberecht. Dieses besagt, dass die Abgabe entsprechend dem Gesetz erhoben werden muss (<ref-ruling> E. 3 S. 251), schliesst aber eine Wiedererwägung wegen zweifellos unrichtiger Rechtsanwendung nicht aus, sondern spricht im Gegenteil für eine solche, weil sonst ein materiell rechtswidriger Zustand bestehen bliebe. Dies wäre nicht durch das Legalitätsprinzip geschützt, sondern allenfalls durch den Grundsatz von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV; vgl. auch zum daraus abgeleiteten Vertrauensschutz <ref-ruling> E. 5 S. 474), der aber verbindlich (<ref-law>) durch das Bundesgesetz konkretisiert wird und grundsätzlich nicht angerufen werden kann, wenn dieses eine Wiedererwägung vorsieht (SZS 2006 S. 474, E. 4.5, U 378/05). Diese steht zudem nicht im freien Belieben der Behörden, sondern verlangt stets eine zweifellose Unrichtigkeit und eine erhebliche Bedeutung der Berichtigung (SVR 2008 AHV Nr. 17 S. 51 E. 4, H 168/06; Urteile 8C_512/2008 vom 14. Januar 2009 E. 6.1 und 9C_575/2007 vom 18. Oktober 2007 E. 2.2; vgl. auch <ref-ruling> E. 2c S. 469, 122 V 19 E. 3a S. 21 mit Hinweisen).
2.3 Was die Wiedererwägungsvoraussetzung der erheblichen Bedeutung der Berichtigung betrifft, ist diese angesichts der Höhe der Beiträge, die mit den Nachtragsverfügungen auf zusätzlichen Einkommen von Fr. 150'000.- (2002), Fr. 177'452.- (2003) und Fr. 145'373.- (2004) erhoben wurden, ohne Weiteres erfüllt.
2.4 Die Voraussetzung der zweifellosen Unrichtigkeit ist unter anderem bei unrichtiger Rechtsanwendung gegeben (<ref-ruling> E. 2b/bb S. 401; Urteile U 378/05 E. 5.3; 9C_910/2007 E. 4). Nicht erforderlich ist, dass sie offensichtlich ist (KIESER, ATSG-Kommentar, Zürich 2003, N 31 zu Art. 53). Wie sich aus dem Folgenden ergibt, ist auch diese Voraussetzung hier erfüllt:
3. 3.1 Gemäss <ref-law> werden die Beiträge der erwerbstätigen Versicherten in Prozenten des Einkommens aus unselbstständiger und selbstständiger Erwerbstätigkeit festgesetzt (Abs. 1). Als Ausnahme zu diesem Grundsatz kann der Bundesrat gemäss Abs. 2 lit. a dieser Bestimmung das Erwerbseinkommen aus einer im Ausland ausgeübten Tätigkeit von der Beitragsbemessung ausnehmen. Eine solche Ausnahme von der Beitragserhebung besteht gemäss dem seit 1. Juni 2002 geltenden <ref-law> für Erwerbseinkommen, das Personen mit Wohnsitz in der Schweiz als Inhaber oder Teilhaber von Betrieben oder von Betriebsstätten in einem Nichtvertragsstaat zufliesst. Dieser Artikel wurde im Zusammenhang mit dem Inkrafttreten der bilateralen Verträge mit der EU eingefügt. Aus diesem Zusammenhang ergibt sich auch, dass Vertragsstaat im Sinne dieser Bestimmung die EU-Staaten meint. Einkommen aus einer Betriebsstätte in Deutschland sind demzufolge seit 1. Juni 2002 nicht mehr von der Beitragserhebung ausgenommen.
3.2 Dies entspricht der staatsvertraglichen Regelung: Nach Art. 8 und Anhang II des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) in Verbindung mit Art. 13 Abs. 2 lit. b der 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 (Verordnung Nr. 1408/71; SR 0.831.109.268) unterliegen Personen, die eine selbstständige Tätigkeit gewöhnlich im Gebiet von zwei oder mehr Vertragsstaaten ausüben, den Rechtsvorschriften derjenigen Vertragsstaaten, in dem sie wohnen, wenn sie ihre Tätigkeit zum Teil in diesem Gebiet ausüben (Art. 14a Abs. 2 der Verordnung Nr. 1408/71). Diese Regelung bezweckt, dass ein und dieselbe Person für einen bestimmten Zeitraum immer nur dem Sozialversicherungsrecht eines der beteiligten Staaten unterstellt ist (vgl. <ref-ruling> E. 3.1), auch in Bezug auf die Beitragspflicht (vgl. Edgar Imhof, FZA/EFTA-Übereinkommen und soziale Sicherheit, in: Jusletter vom 23. Oktober 2006, Rz. 11 und 36; derselbe, Über die Kollisionsnorm der Verordnung 1408/71 [anwendbares Sozialrecht, zugleich Versicherungsunterstellung], SZS 2008 S. 313ff., 316, 319 f.). Dies hat zur Folge, dass nun - sofern auf eine Person das schweizerische Recht anwendbar ist - das gesamte selbständige Erwerbseinkommen dieser Person der schweizerischen AHV-Beitragspflicht untersteht, auch wenn es in einem anderen Vertragsstaat erzielt worden ist. Die vorher auf Grund von internationalen Sozialversicherungsabkommen geltende Regelung, wonach das Einkommen den Regeln desjenigen Staates untersteht, in welchem es erzielt wurde (Erwerbsortsprinzip, vgl. H 158/05 vom 4. Mai 2007, E. 5.1 mit Hinweisen), ist damit ab 1. Juni 2002 im Falle, da eine Person in mehreren Vertragsstaaten gleichzeitig ein selbständiges Einkommen erzielt, nicht mehr gültig (Art. 20 FZA; Urteil H 177/06 vom 28. September 2007 E. 4 mit Hinweisen; Silvia Bucher, Die sozialrechtliche Rechtsprechung des Bundesgerichts zum FZA und zu Anhang K des EFTA-Übereinkommens, SZS 2008 S. 409 ff., 424), anders bei selbständiger Tätigkeit im einen und unselbständiger Tätigkeit in einem anderen Staat, (FZA Anhang II Abschnitt A Ziff. 1 lit. p i.V.m Art. 14 c lit. b und Anhang VII der Verordnung Nr. 1408/71).
3.3 Unbestritten hat der Beschwerdeführer Wohnsitz in der Schweiz und übt eine selbständige Erwerbstätigkeit hier und in Deutschland aus. Er unterliegt daher nach der dargelegten Rechtslage für das ganze Erwerbseinkommen dem schweizerischen Recht. Die staatsvertragliche Regelung weicht im Sozialversicherungsrecht von derjenigen im Steuerrecht ab. Es ist auch weder nach Staatsvertragsrecht noch nach Landesrecht von Bedeutung, ob das betreffende Einkommen nach deutschem Recht der Beitragspflicht unterstünde.
Es ist im vorliegenden Zusammenhang darauf hinzuweisen, dass Art. 42 EG (= Vertrag zur Gründung der Europäischen Gemeinschaft in der Fassung nach In-Kraft-Treten des eine Umnummerierung der Artikel bewirkenden Vertrages von Amsterdam am 1. Mai 1999) (alt Art. 51 EG-Vertrag [= Vertrag zur Gründung der Europäischen Gemeinschaft in der Fassung vor In-Kraft-Treten des Vertrages von Amsterdam]), auf den sich die Verordnung Nr. 1408/71 insbesondere stützt, lediglich eine Koordinierung, nicht aber eine Harmonisierung der Rechtsvorschriften der Mitgliedstaaten auf dem Gebiet der sozialen Sicherheit vorsieht, sodass die materiellen und formellen Unterschiede zwischen den Systemen der sozialen Sicherheit der einzelnen Mitgliedstaaten und folglich zwischen den Ansprüchen und Pflichten der dort Beschäftigten bestehen bleiben (z. B. Urteil des EuGH vom 19. März 2002 in den Rechtssachen C-393/99 und C-394/99, Hervein u. a., Slg. 2002, I-2829, Randnr. 50 mit Hinweisen). Das Gemeinschaftsrecht, welches hinsichtlich der Koordinierung der Systeme der sozialen Sicherheit vom FZA übernommen wurde, lässt die Zuständigkeit der Mitgliedstaaten zur Ausgestaltung ihrer Systeme der sozialen Sicherheit unberührt; mangels einer Harmonisierung auf Gemeinschaftsebene bestimmt das Recht jedes Mitgliedstaats, unter welchen Voraussetzungen zum einen ein Recht auf Anschluss an ein System der sozialen Sicherheit oder eine Verpflichtung hierzu besteht und zum anderen Leistungen der sozialen Sicherheit gewährt werden; gleichwohl müssen die Mitgliedstaaten bei der Ausübung dieser Befugnis das Gemeinschaftsrecht beachten (<ref-ruling> E. 3.1 S. 432; <ref-ruling> E. 7.1 S. 432; <ref-ruling> E. 5.3 S. 213). Wenn der Beschwerdeführer nach schweizerischem Recht für Einkommensbestandteile AHV-Beiträge entrichten muss, die nach deutschem Recht nicht der Beitragspflicht unterstünden, so ist das eine Konsequenz der schweizerischen Gesetzgebung, welche in diesem Punkt zulässigerweise von derjenigen anderer Staaten abweichen kann. In der Anwendung schweizerischer Gesetzgebung auf die dem schweizerischen Recht unterstehenden Sachverhalte liegt keine Diskriminierung, auch wenn dadurch die Betroffenen schlechter gestellt sind, als sie bei Anwendung des ausländischen Rechts wären; das ist vielmehr unvermeidliche Konsequenz davon, dass Staaten auf Grund ihrer Souveränität Gesetze erlassen können, die sich von den in anderen Staaten geltenden Gesetzen unterscheiden.
Schliesslich ist auch der Umstand, dass der Beschwerdeführer Beiträge weit über dem rentenbildenden Maximum entrichtet und seine höheren Beiträge somit nicht mehr zu besseren Versicherungsleistungen für ihn persönlich führen können, sondern einzig der Finanzierung der AHV dienen, kein Grund, das Gesetz nicht anzuwenden oder die zweifellose Unrichtigkeit der ursprünglichen Verfügungen zu verneinen. Dass in der AHV die Beiträge nicht begrenzt, die Renten jedoch plafoniert sind, und die Versicherten, die sich über einer bestimmten Einkommensgrenze bewegen, nicht rentenbildende Beiträge bezahlen, sondern damit als wirtschaftlich bessergestellte Personen indirekt die Renten von weniger gut situierten Versicherten finanzieren, ist vielmehr Ausdruck des der gesetzlichen Regelung der schweizerischen Alters- und Hinterlassenenversicherung zu Grunde liegenden Solidaritätsprinzips (vgl. dazu Botschaft des Bundesrates an die Bundesversammlung zum Entwurf eines Bundesgesetzes über die Alters- und Hinterlassenenversicherung vom 24. Mai 1946, BBl 1946 II 383, 434 sowie Botschaft zur Änderung des Bundesgesetzes über die Alters- und Hinterlassenenversicherung vom 28. April 1999, BBl 1999 4990).
3.4 Der Beschwerdeführer führt unter Berufung auf <ref-law> aus, es dürfe nicht das gesamte weltweite Erwerbseinkommen zu Grunde gelegt werden, sondern nur dasjenige, das nach der rechtskräftigen Steuerveranlagung in der Schweiz zu versteuern sei. Dies ist offensichtlich unbegründet. Die Angaben der Steuerbehörden sind für die Ausgleichskassen in Bezug auf die Bemessung des massgebenden Einkommens und des betrieblichen Eigenkapitals verbindlich, nicht aber in Bezug auf die betragsrechtliche Qualifikation (relative Bindung des Sozialversicherungsgerichts an die rechtskräftigen Steuertaxationen; <ref-ruling> E. 2c S.83, 114 V 72 E. 2 S. 75, 110 V 83 E. 4 S. 86 und 369 E. 2a S. 370, 102 V 27 E. 3b S. 31, je mit Hinweisen; Urteil H 36/03 vom 7. Juni 2004 E. 4.5). Unterliegt ein Einkommen nach der massgebenden rechtlichen Lage nicht der Steuerpflicht, wohl aber der Beitragspflicht, so kann von vornherein die ahv-rechtliche Betrachtung nicht auf das gemäss Steuerveranlagung steuerbare Einkommen abstellen. Zutreffend ist, dass nicht das gesamte weltweit erzielte Einkommen zu Grunde gelegt werden darf, sondern nur das in Vertragsstaaten erzielte Erwerbseinkommen. Indessen macht der Beschwerdeführer nicht geltend, in der streitigen Veranlagung seien auch andere Einkommensteile erfasst als die aus seiner Erwerbstätigkeit in Deutschland stammenden. Auch sonst ist die Höhe der Beiträge nicht bestritten.
4. Im Eventualstandpunkt beantragt der Beschwerdeführer die Aufhebung der Verfügung für das Jahr 2002.
4.1 Die Beschwerdegegnerin hat in der Rektifikatsverfügung vom 20. Dezember 2007 das gesamte im Jahr 2002 in Deutschland erzielte Erwerbseinkommen berücksichtigt, obwohl - wie dargelegt - dieses Einkommen erst ab 1. Juni 2002 der Beitragspflicht unterliegt. Im Einspracheentscheid wurde dies richtigerweise korrigiert. Die Einsprache wurde gutgeheissen, soweit in Deutschland erzieltes Erwerbseinkommen mitberücksichtigt wurde, welches vom 1. Januar bis 31. Mai 2002 in Deutschland erzielt wurde. In den Erwägungen des Einspracheentscheides führte die Ausgleichskasse aus, für die Ausscheidung des bis 31. Mai 2002 erzielten Einkommens sei der belegmässige Nachweis zu erbringen; sie werde die Verfügung 2002 anpassen, sobald sie im Besitz der erforderlichen Belege sei. In der kantonalen Beschwerde hatte der Beschwerdeführer beantragt, es sei die Verfügung für das ganze Jahr 2002 aufzuheben, weil eine Ausscheidung des auf die Zeit bis 31. Mai entfallenden Einkommens nicht möglich sei. Die Vorinstanz führte dazu aus, dies sei eine reine Schutzbehauptung; der Beschwerdeführer werde gut daran tun, sein Einkommen für den beitragsfreien Zeitraum nachvollziehbar und schlüssig aufzuzeigen, ansonsten wohl andere sachlich vertretbare Bemessungsmethoden wie die zeitlich gleichmässige Zuordnung Platz greifen müssten. Letztinstanzlich wiederholt der Beschwerdeführer seine Ausführungen und kritisiert, die Vorinstanz sei sich nicht bewusst, welchen Aufwand das nachträgliche Erstellen eines Zwischenabschlusses nach sich ziehen würde.
4.2 Es ist auch seitens der Beschwerdegegnerin nicht bestritten, dass der Beschwerdeführer für das in Deutschland erzielte Einkommen erst ab 1. Juni 2002 Beiträge schuldet. Grundsätzlich trägt die Ausgleichskasse die Beweislast für das Vorliegen der Umstände, aus denen sie eine Beitragspflicht ableitet, wobei aber dem Beitragspflichtigen eine Mitwirkungspflicht obliegt (<ref-law>), namentlich indem er Jahresabschlüsse vorlegt (<ref-law> in Verbindung mit <ref-law> und <ref-law>). Steuer- und ahv-rechtlich ist der Pflichtige grundsätzlich nicht gehalten, pro Jahr mehr als einen Jahresabschluss zu erstellen (Art. 210 Abs. 2 und 3 DBG; Art. 22 Abs. 3 und 4 AHVV). Es kann vom Beschwerdeführer somit nicht verlangt werden, dass er per 31. Mai 2002 einen Zwischenabschluss erstellt. Das kann jedoch nicht zur Folge haben, dass entgegen der dargelegten rechtlichen Lage auch das von Juni bis Dezember 2002 erzielte Einkommen beitragsfrei bliebe. Vielmehr drängt sich - wie die Vorinstanz mit Recht erwogen hat - eine Umrechnung des Jahreseinkommens auf die sieben Monate der Beitragspflicht auf. Dies entspricht auch der Regelung, wie sie in <ref-law> vorgesehen ist für den Fall, dass in einem Beitragsjahr kein Geschäftsabschluss erstellt wird. Der Beschwerdeführer wird somit entweder der Beschwerdegegnerin einen aussagekräftigen Zwischenabschluss vorlegen oder andernfalls für das in Deutschland erzielte Erwerbseinkommen 2002 pro rata der Beitragspflicht unterliegen.
5. Der Beschwerdeführer als unterliegende Partei hat die Gerichtskosten zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3500.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 2. September 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Helfenstein Franke