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.