Sachverhalt:
A. Der 1967 geborene B._ bezog seit dem 1. Januar 1999 eine halbe Rente der Invalidenversicherung. Mit Verfügungen vom 12. April 2006 sprach ihm die IV-Stelle des Kantons Graubünden im Rahmen eines Rentenrevisionsverfahrens ab 1. Januar 2004 eine Dreiviertelsrente zu mit dem Hinweis, dass die Abklärungen für den Zeitraum resp. den Rentenanspruch ab 1. Mai 2005 fortgesetzt würden. Nach Durchführung des Vorbescheidverfahrens hob sie die Rente mit Verfügungen vom 3./25. November 2008 auf das Ende des der Zustellung folgenden Monats auf.
B. Die Beschwerde des B._ wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 19. Mai 2009 ab.
C. B._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, unter Aufhebung des Entscheids vom 19. Mai 2009 und der Verfügungen vom 3. und 25. November 2008 sei ihm über den 31. Dezember 2008 hinaus weiterhin eine Dreiviertelsrente der Invalidenversicherung auszurichten; eventualiter sei die Sache zwecks weiterer Abklärung an die Verwaltung zurückzuweisen.
Die IV-Stelle und das kantonale Gericht schliessen auf Abweisung der Beschwerde, das Bundesamt für Sozialversicherungen verzichtet auf eine Stellungnahme.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). 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 Artikel 95 beruht (Art. 105 Abs. 2 BGG).
2. Die Vorinstanz hält die Verfügungen vom 3. und 25. November 2008, mit welchen die Invalidenrente auf Ende Dezember 2008 aufgehoben wurde, für rechtens. Sie ist der Auffassung, die im Gutachten des ärztlichen Begutachtungsinstituts X._ vom 18. September 2007 ausgewiesene positive Entwicklung des Gesundheitszustandes des Versicherten stelle klarerweise einen Grund für die Rentenrevision dar. Demgegenüber stellt der Beschwerdeführer das Vorliegen eines Revisionsgrundes in Abrede und macht geltend, es werde lediglich der unveränderte Sachverhalt unterschiedlich beurteilt. Ausserdem bestreitet er den Beweiswert des Gutachtens des ärztlichen Begutachtungsinstituts X._.
3. 3.1 Ändert sich der Invaliditätsgrad einer Rentenbezügerin oder eines Rentenbezügers erheblich, so wird die Rente von Amtes wegen oder auf Gesuch hin für die Zukunft entsprechend erhöht, herabgesetzt oder aufgehoben (Art. 17 Abs. 1 ATSG). Anlass zur Rentenrevision gibt jede wesentliche Änderung in den tatsächlichen Verhältnissen seit Zusprechung der Rente, die geeignet ist, den Invaliditätsgrad und damit den Anspruch zu beeinflussen. Insbesondere ist die Rente bei einer wesentlichen Änderung des Gesundheitszustandes oder der erwerblichen Auswirkungen des an sich gleich gebliebenen Gesundheitszustandes revidierbar (<ref-ruling> E. 3.5 S. 349 mit Hinweisen). Dagegen stellt die unterschiedliche Beurteilung der Auswirkungen eines im Wesentlichen unverändert gebliebenen Gesundheitszustandes auf die Arbeitsfähigkeit keinen Revisionsgrund im Sinne von Art. 17 Abs. 1 ATSG dar (Urteil 9C_552/2007 vom 17. Januar 2008 E. 3.1.2 mit Hinweisen).
Liegt eine erhebliche Änderung des Sachverhalts vor, ist der Rentenanspruch in rechtlicher und tatsächlicher Hinsicht allseitig, d.h. unter Berücksichtigung des gesamten für die Leistungsberechtigung ausschlaggebenden Tatsachenspektrums, zu prüfen (<ref-ruling> E. 4b S. 200; SVR 2004 IV Nr. 17 S. 53, I 526/02 E. 2.3; Urteil 9C_744/2008 vom 19. November 2008 E. 3.1.1; vgl. auch <ref-ruling> E. 2d S. 417 f.; AHI 2002 S. 164, I 652/00 E. 2a).
3.2 Die Vorinstanz hat gestützt auf das Gutachten des ärztlichen Begutachtungsinstituts X._, welches sie diesbezüglich in freier Beweiswürdigung (Art. 61 lit. c ATSG) und Übereinstimmung mit der Rechtsprechung (<ref-ruling> E. 3a S. 352) als schlüssig, zuverlässig und einleuchtend erachtet hat, festgestellt, einige der früher diagnostizierten Leiden - insbesondere die Depressionen und psychischen Stimmungsschwankungen - seien inzwischen verschwunden. Diese Feststellung ist nicht offensichtlich unrichtig und daher für das Bundesgericht verbindlich (E. 1): Aus dem Gutachten der Klinik Y._ vom 22. April 2004, welches der Rentenverfügung vom 12. April 2006 zugrunde lag, geht u.a. eine ängstliche, Belastung übermässig vermeidende Schmerzbewältigung und eine "Entwicklung depressiver Symptome mit sozialem Rückzug, einer ausgeprägten Grübelneigung, einer gedrückten Stimmungslage sowie Suizidgedanken" hervor, welche eine "psychiatrische Behandlung mit einer medikamentösen antidepressiven Therapie sowie begleitenden psychotherapeutischen Gesprächen" erforderte. Es wurden eine Anpassungsstörung mit längerer depressiver Reaktion (ICD-10: F43.21) sowie akzentuierte Persönlichkeitszüge mit perfektionistischen und narzisstischen Zügen (ICD-10: Z73.1) diagnostiziert und die Weiterführung der psychiatrischen/psychotherapeutischen Behandlung empfohlen. Diese psychischen Faktoren waren - nebst einem chronifizierten Panvertebralsyndrom ohne lumboradikuläre Reiz- oder Ausfallsymptomatik bei leichtgradiger Wirbelsäulenfehlform und -haltung sowie muskulärer Dysbalance - offensichtlich wesentlich für die Beurteilung der Arbeitsfähigkeit, welche die Ärzte damals für leichte bis maximal mittelschwere Tätigkeiten auf 50 % veranschlagt hatten. Demgegenüber ist aus dem Gutachten des ärztlichen Begutachtungsinstituts X._ ersichtlich, dass der Versicherte nunmehr weder unter Schlaf-, Antriebs- oder Konzentrationsstörungen, einem sozialen Rückzug oder depressiven Verstimmungen leidet, noch in psychiatrischer Behandlung steht. Mit Bezug auf die psychischen Beschwerden wurde einzig eine anhaltende somatoforme Schmerzstörung (ICD-10: F45.4) diagnostiziert und die Indikation einer medizinischen Behandlung ausdrücklich verneint. Unter diesen Umständen hat das kantonale Gericht zu Recht eine relevante Verbesserung des Gesundheitszustandes angenommen.
Daran ändert nichts, dass die Vorinstanz keinen ausführlichen Vergleich der medizinischen Sachverhalte (für den jeweiligen Zeitpunkt vgl. <ref-ruling>) vorgenommen hat; der Schluss auf einen verbesserten Gesundheitszustand beruht auf einer zulässigen impliziten Gegenüberstellung der aus den massgeblichen Grundlagen (Gutachten der Klinik Y._ vom 22. April 2004 und Gutachten des ärztlichen Begutachtungsinstituts X._ vom 18. September 2007) ersichtlichen Tatsachen und entspricht auch der Auffassung des Regionalen Ärztlichen Dienstes (vgl. Art. 59 Abs. 2bis IVG und Art. 49 Abs. 1 IVV). Weiter schadet nicht, dass im Gutachten des ärztlichen Begutachtungsinstituts X._ der Sachverhalt - in psychiatrischer Hinsicht - mit demjenigen verglichen wurde, welcher sich anlässlich der im Oktober 1999 erfolgten Begutachtung durch die MEDAS bot (vgl. Gutachten vom 18. November 1999): Die damals erhobenen Befunde und Einschätzungen, welche Grundlage für die Annahme einer um 32,5 % reduzierten Arbeitsfähigkeit und folglich die erstmalige Bejahung des Rentenanspruchs bildeten (vgl. Verfügung vom 9. März 2000), stimmen weitgehend mit jenen der Klinik Y._ überein. Schliesslich spricht die sachlich begründete, kritische Auseinandersetzung des Rheumatologen mit früheren ärztlichen Einschätzungen - wie auch die Kritik an der darauf beruhenden Rentenerhöhung - nicht für mangelnde Objektivität des Sachverständigen, sondern im Gegenteil für die Qualität des Gutachtens des ärztlichen Begutachtungsinstituts X._ (<ref-ruling> E. 3a S. 352). Dass daraus der Schluss auf einen aus rheumatologischer Sicht seit Jahren unveränderten Gesundheitszustand zu ziehen ist, berührt indessen nicht die festgestellte Verbesserung in Bezug auf die psychischen Beschwerden, welche Anlass für eine umfassende Überprüfung der Leistungsberechtigung gibt.
3.3 Nach dem Gesagten hat die Vorinstanz zu Recht die Verfügung vom 3. November 2008 - welche gestützt auf die Einschätzung der Gutachter des ärztlichen Begutachtungsinstituts X._ (uneingeschränkte Arbeitsfähigkeit für jegliche leichten bis auch regelmässig mittelschweren, wechselbelastenden Tätigkeiten) einen rentenausschliessenden (Art. 28 IVG) Invaliditätsgrad von 24 % ausweist - sowie jene vom 25. November 2008 bestätigt. Die Beschwerde ist unbegründet.
4. Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG).

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