Faits: A. A.a M._ a été mis au bénéfice d'une demi-rente de l'assurance-invalidité à partir du 1er février 1999 jusqu'au 31 mai 2001 en raison de troubles psychiques (décision de l'Office de l'assurance-invalidité pour le canton de Vaud [ci-après: office AI] du 29 octobre 2001, réformée par jugement du Tribunal des assurances du canton de Vaud du 2 juillet 2002, en ce sens que le droit à la prestation a été accordé au-delà du 31 mai 2001). A l'époque, les médecins avaient diagnostiqué un état dépressif majeur d'intensité légère à moyenne, une dysthymie et une personnalité immature à traits paranoïaques et limite, atteintes qui limitaient à 50 % la capacité de travail de l'assuré dans l'activité de manutentionnaire exercée jusqu'alors (cf. jugement cantonal du 2 juillet 2002). A.b Le 3 octobre 2002, alors qu'il travaillait à mi-temps en qualité d'aide-magasinier au service de la société X._ SA, M._ a été victime d'un accident qui a entraîné de multiples fractures costales provoquant une pseudarthrose de la 6ème à la 10ème côte du flanc droit. En tant qu'assureur-accidents, la Caisse nationale suisse d'assurance en cas d'accidents (CNA) a pris en charge les suites de cet événement. Elle a alloué à M._ une rente fondée sur un taux d'invalidité de 45 % à partir du 1er février 2004 (décision du 29 juin 2004). Saisi en parallèle d'une demande de révision de la part de l'assuré, l'office AI a recueilli divers avis médicaux et requis l'avis de son Service médical régional AI (SMR), où le docteur U._ a indiqué que l'intéressé disposait, après une alternance de périodes d'incapacité totale et partielle de travail, d'une capacité de travail globale (psychique et physique) de 50 % dans une activité adaptée à partir du 29 juin 2004. De leur côté, les doctoresses U._ et L._ de l'Hôpital Y._ ont fait état d'une aggravation de l'état de santé psychique et d'une incapacité totale de travail au moins depuis le 8 avril 2005 (début du suivi psychiatrique; rapport du 3 août 2005). Par décision du 23 novembre 2007, l'office AI a reconnu à M._ un droit à une rente entière d'invalidité du 1er octobre 2003 au 30 septembre 2004 (remplacée à partir du 1er octobre 2004 par une demi-rente). B. L'assuré a déféré cette décision au Tribunal des assurances du canton de Vaud (depuis le 1er janvier 2009, Cour des assurances sociales du Tribunal cantonal), en concluant à l'octroi d'une rente entière d'invalidité au-delà de septembre 2004. Par jugement du 10 novembre 2008, le Tribunal a admis le recours et réformé la décision administrative, en ce sens que le droit à la rente entière d'invalidité était maintenu au-delà du 30 septembre 2004. C. L'office AI interjette un recours en matière de droit public contre le jugement cantonal, dont il demande l'annulation. Il conclut à la confirmation de sa décision du 23 novembre 2007. Il sollicite par ailleurs l'effet suspensif à son recours, ce qui lui a été accordé par ordonnance du 31 mars 2009 en tant que l'effet suspensif porte sur le versement de prestations supérieures à une demi-rente d'invalidité. M._ conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.