Sachverhalt:
A. Der 1958 geborene E._ war vom 1. April 1995 bis 30. Oktober 1996 Angestellter der Y._ AG und deswegen bei der Pensionskasse X._ (nachfolgend PK X._) für die berufliche Vorsorge versichert. Wegen psychischer Beeinträchtigungen war er seit Mitte September 1995 teilweise oder vollständig arbeitsunfähig. Nachdem verschiedene berufliche Eingliederungsmassnahmen gescheitert waren, sprach ihm die IV-Stelle des Kantons St. Gallen bei einem Invaliditätsgrad von 56 % vom 1. September 1996 bis 31. Dezember 2000 eine halbe sowie unter Zugrundelegung einer Invalidität von 71 % ab 1. Januar 2001 eine ganze Rente der Invalidenversicherung zu (Verfügungen vom 29. März 1999 und 28. August 2002). Demgegenüber verweigerte die PK X._ Invalidenleistungen aus beruflicher Vorsorge, weil die massgebliche Arbeitsunfähigkeit schon vor Stellenantritt bei der Firma Y._ eingetreten sei.
Am 4. November 2004 liess E._ gesetzliche und reglementarische Invalidenleistungen (nebst Zins) mit Klage gegen die PK X._ geltend machen, welche das Verwaltungsgericht des Kantons Bern mit Entscheid vom 4. Juli 2006 abwies. In Gutheissung der dagegen erhobenen Verwaltungsgerichtsbeschwerde bejahte das Bundesgericht mit Urteil B 95/06 vom 4. Februar 2008 die Leistungspflicht der PK X._ und wies die Sache an die Vorinstanz zurück, damit diese im Sinne der Erwägungen verfahre und über die Klage vom 4. November 2004 neu entscheide.
B. In Gutheissung der Klage vom 4. November 2004 sprach das Verwaltungsgericht des Kantons Bern mit Entscheid vom 27. Mai 2009 E._ ab 1. November 1998 eine überobligatorische Invalidenrente bei einem Invaliditätsgrad von 56 % und ab 1. Januar 2001 zusätzlich den Betrag einer halben obligatorischen Invalidenrente nach BVG zu, wobei die PK X._ den genauen Betrag festzusetzen haben werde (Dispositiv-Ziffer 1). Weiter wurde die PK X._ verpflichtet, auf den auszurichtenden Rentenleistungen ab 4. November 2004 einen Verzugszins von 5 % zu bezahlen (Dispositiv-Ziffer 2), ein Vergleich über die Berechnung der Überentschädigung gerichtlich genehmigt (Dispositiv-Ziffer 3) und - unter Verzicht auf die Erhebung von Gerichtskosten (Dispositiv-Ziffer 4) - E._ eine Parteientschädigung von Fr. 1'000.- zugesprochen (Dispositiv-Ziffer 5).
C. Die PK X._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, unter Aufhebung der Dispositiv-Ziffern 1 und 5 des Entscheides vom 27. Mai 2009 sei E._ ab 1. November 1998 und auch ab 1. Januar 2001 eine überobligatorische Invalidenrente auf der Basis eines Invaliditätsgrades von 56 % zuzusprechen und zu verpflichten, ihr für das vorinstanzliche Verfahren eine Parteientschädigung zu bezahlen.
E._ lässt die Abweisung der Beschwerde beantragen. Die Vorinstanz und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem 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 Artikel 95 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 zu Grunde, 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 Artikel 95 beruht (<ref-law>).
2. Es steht fest und ist unbestritten, dass der (durch die Organe der Invalidenversicherung festgestellte) Invaliditätsgrad nach Beendigung des Vorsorgeverhältnisses von 56 auf 71 % angestiegen und die Beschwerdeführerin dafür grundsätzlich leistungspflichtig ist. Streitig und zu prüfen ist die Auswirkung dieser Erhöhung auf den Umfang der von der PK X._ ab 1. Januar 2001 auszurichtenden Invalidenrente.
3. 3.1 Nach Art. 23 BVG (in der hier anwendbaren, bis 31. Dezember 2004 geltenden Fassung) hat Anspruch auf eine Invalidenrente, wer im Sinne der Invalidenversicherung zu mindestens 50 % invalid ist und bei Eintritt der Arbeitsunfähigkeit, deren Ursache zur Invalidität geführt hat, versichert war. Entscheidend im Rahmen von Art. 23 BVG ist einzig der Eintritt der relevanten Arbeitsunfähigkeit (zu diesem Begriff vgl. <ref-ruling> E. 3.1 S. 345 f. mit Hinweisen; SZS 2003 S. 521, B 49/00 E. 3), unabhängig davon, in welchem Zeitpunkt und in welchem Masse daraus ein Anspruch auf Invalidenleistungen entsteht. Die Versicherteneigenschaft muss nur bei Eintritt der Arbeitsunfähigkeit gegeben sein, dagegen nicht notwendigerweise auch im Zeitpunkt des Eintritts oder der Verschlimmerung der Invalidität. Für eine einmal aus - während der Versicherungsdauer aufgetretener - Arbeitsunfähigkeit geschuldete Invalidenleistung bleibt die Vorsorgeeinrichtung somit leistungspflichtig, selbst wenn sich nach Beendigung des Vorsorgeverhältnisses der Invaliditätsgrad ändert. Entsprechend bildet denn auch der Wegfall der Versicherteneigenschaft keinen Erlöschungsgrund (Art. 26 Abs. 3 BVG e contrario; <ref-ruling> E. 1a S. 263; <ref-ruling> E. 5 S. 45). Die Leistungspflicht einer Vorsorgeeinrichtung für eine erst nach Beendigung des Vorsorgeverhältnisses eingetretene oder verschlimmerte Invalidität setzt indessen in jedem Fall voraus, dass zwischen relevanter Arbeitsunfähigkeit und nachfolgender Invalidität ein enger sachlicher und zeitlicher Zusammenhang besteht (<ref-ruling> E. 1c S. 264 f.; <ref-ruling> E. 2c/aa und bb S. 117 f. mit Hinweisen), was das Bundesgericht im konkreten Fall mit Urteil B 95/06 vom 4. Februar 2008 bejahte.
3.2 Mit Bezug auf die weitergehende berufliche Vorsorge steht es den Vorsorgeeinrichtungen im Rahmen von Art. 6 und Art. 49 Abs. 2 BVG sowie der verfassungsmässigen Schranken (wie Rechtsgleichheit, Willkürverbot und Verhältnismässigkeit) frei, den Invaliditätsbegriff und/oder das versicherte Risiko abweichend von Art. 23 BVG (vgl. E. 3.1) zu definieren (SZS 1997 S. 557, B 40/93 E. 4a; <ref-ruling> E. 3c S. 108 f. mit Hinweisen). Während sie im Rahmen der obligatorischen beruflichen Vorsorge jedenfalls die Mindestvorschrift des Art. 23 BVG zu beachten haben (Art. 6 BVG), gilt diese Bestimmung einschliesslich der hierzu ergangenen Rechtsprechung im überobligatorischen Bereich nur, soweit die Reglemente oder Statuten bezüglich des massgebenden Invaliditätsbegriffs oder versicherten Risikos nichts Abweichendes vorsehen (vgl. <ref-ruling> E. 1b S. 264; SZS 2006 S. 144, B 33/03 E. 3.2).
3.3 Im hier massgeblichen (vgl. die Übergangsbestimmung in Art. 32 Abs. 1 des Reglements vom 1. Januar 2000) Reglement vom 1. Januar 1995 - dessen Bestimmungen nur für den "das Obligatorium/BVG übersteigenden Teil" anwendbar sind (Art. 2 Abs. 4 des Reglements) - ist der Anspruch auf eine Invalidenrente wie folgt geregelt: Ein Versicherter gilt als invalid, wenn er aus gesundheitlichen Gründen seine bisherige oder eine andere seinem Wissen und Können entsprechende Erwerbstätigkeit nicht mehr ausüben kann und er deshalb vor Erreichen des Rentenalters aus dem Dienst entlassen oder in eine Stellung mit niedrigerem Lohn versetzt wird (Art. 7 Abs. 1 des Reglements). Dabei gilt u.a. eine Verminderung der Arbeitsfähigkeit um weniger als ein Fünftel nicht als Invalidität (Art. 7 Abs. 2 des Reglements). Wird ein Versicherter in diesem Sinn invalid, so erhält er eine Invalidenrente (Art. 15 Abs. 1 Satz 1 des Reglements). Für einen Vollinvaliden ist die Vollinvalidenrente gleich der Altersrente; für einen teilinvaliden Versicherten ist die Teilinvalidenrente gleich demjenigen Teil der Altersrente, der dem jeweiligen Invaliditätsgrad entspricht (Art. 15 Abs. 1 Satz 3 des Reglements). Eine Bestimmung über die Rentenrevision bei verändertem Invaliditätsgrad fehlt in diesem Reglement.
3.4 Die Vorinstanz hat zutreffend festgehalten, dass der Versicherte - entsprechend der Verfügung der Invalidenversicherung vom 28. August 2002 - ab 1. Januar 2001 bei einem Invaliditätsgrad von 71 % (mindestens) Anspruch auf eine volle Rente der obligatorischen beruflichen Vorsorge hat. In Bezug auf die weitergehende Vorsorge ist sie der Auffassung, nach Art. 15 Ziff. 1 in Verbindung mit Art. 7 Ziff. 1 des Vorsorgereglements führe im konkreten Fall das Fortschreiten der Krankheit zu keiner Erhöhung der Vorsorgeleistungen.
3.5 Die Auslegung der reglementarischen Bestimmungen (vgl. <ref-ruling> E. 6.2 S. 375 mit weiteren Hinweisen; zur Qualifizierung als Rechtsfrage vgl. Urteil 5A_122/2008 vom 30. Juli 2008 E. 3.3) ergibt, dass im überobligatorischen Bereich der Anspruch auf eine Invalidenrente nicht vom Eintritt der invalidisierenden Arbeitsunfähigkeit (vgl. E. 3.1), sondern vom Eintritt der Invalidität im Sinne des Reglements als versichertem Risiko abhängt. Damit sind nebst einer (teilweisen) Arbeitsunfähigkeit die darauf beruhenden erwerblichen Auswirkungen in Form der genannten Folgen für das Arbeitsverhältnis (zu einem der Vorsorgeeinrichtung angeschlossenen Arbeitgeber) relevant. Ausserdem gilt nach dem Wortlaut des Reglements nur ein "Versicherter" als invalid. Daraus ist in zeitlicher Hinsicht zu schliessen, dass die Invalidität jedenfalls vor Beendigung des Versicherungsverhältnisses eingetreten sein muss (SZS 2006 S. 144, B 33/03 E. 4.3.2). Knüpft der reglementarische Invaliditätsbegriff - wie im konkreten Fall - an ein konkretes Arbeitsverhältnis und die Versicherteneigenschaft des Leistungsansprechers an, ist demnach für eine nach Beendigung des Vorsorgeverhältnisses eingetretene Erhöhung des Invaliditätsgrades mangels einer ausdrücklichen reglementarischen Bestimmung, welche bei verändertem Invaliditätsgrad die Rentenrevision vorsieht, von einer Lücke im Versicherungsschutz aus weitergehender Vorsorge auszugehen (vgl. Urteil B 55/95 des Eidg. Versicherungsgerichts vom 6. Mai 1997 in fine), zumal die Nachhaftung der Vorsorgeeinrichtung für eine Verschlimmerung der Invalidität gemäss Art. 23 BVG (E. 3.1) grundsätzlich nur den obligatorischen Bereich betrifft (vgl. Art. 49 Abs. 2 BVG e contrario) und in der weitergehenden Vorsorge bereits die Abweichung des Invaliditätsbegriffs oder des versicherten Risikos eine andere Regelung implizieren kann (E. 3.2). Dies scheint auch insofern die Auffassung der Beschwerdeführerin gewesen zu sein, als sie in das Reglement vom 1. Januar 2000 erstmals eine explizite Revisionsgrundlage aufnahm (vgl. Art. 12 Abs. 3).
Das Versicherungsverhältnis zwischen der Vorsorgeeinrichtung und dem Beschwerdegegner wurde mit Ablauf der an das auf Ende Oktober 1996 gekündigte Arbeitsverhältnis anschliessenden Nachdeckungsfrist (Art. 10 Abs. 3 BVG) aufgelöst. Die rund 4 Jahre später erfolgte und zu einem Invaliditätsgrad von 71 % führende Verschlechterung des Gesundheitszustandes ist daher (im Gegensatz zum Eintritt der Invalidität im Umfang von 56 %) nicht als Versicherungsfall im Sinne des Reglements aufzufassen; eine Anpassung der Rente aus weitergehender Vorsorge ist demnach ausgeschlossen.
3.6 Nach Auffassung der Vorinstanz wird die eine Hälfte des Anspruchs auf eine volle Rente der obligatorischen beruflichen Vorsorge (vgl. E. 3.4) durch die Ausrichtung der (auf einem Invaliditätsgrad von 56 % beruhenden) reglementarischen Invalidenrente erfüllt, während die andere Hälfte als halbe obligatorische Rente auszurichten ist. Die Beschwerdeführerin macht geltend, dem Anrechnungsprinzip (<ref-ruling> E. 4 S. 266) sei mit der Ausrichtung der (nicht an den höheren Invaliditätsgrad anzupassenden) reglementarischen Leistung von monatlich Fr. 2'093.- Rechnung getragen, diese übertreffe den gesetzlichen Anspruch auf eine volle Invalidenrente, welcher Fr. 1'322.- pro Monat betrage.
3.7 Eine umhüllende Vorsorgeeinrichtung hat die gesetzlichen Leistungen auszurichten, falls diese höher sind als der aufgrund des Reglementes berechnete Anspruch. Andernfalls bleibt es bei der reglementarisch vorgesehenen Leistung (Anrechnungs- oder Vergleichsprinzip; vgl. <ref-ruling> E. 4 S. 267; <ref-ruling> E. 7 und 8 S. 248 ff. mit Hinweisen; SZS 2004 S. 576, B 74/03 E. 3.3.3). Die Anspruchsberechnung hat dabei nicht in der Weise zu erfolgen, dass für den Obligatoriumsbereich und die weitergehende Vorsorge je isolierte Berechnungen angestellt und die Ergebnisse anschliessend addiert werden (Splittings- oder Kumulationsprinzip). Vielmehr sind den sich aus dem Gesetz ergebenden Ansprüchen auf zeitlich identischer Grundlage beruhende (BGE <ref-ruling> E. 9b S. 254) und gleichartige (<ref-ruling> E. 4.2 S. 577; <ref-ruling> E. 4 S. 106 f.), nach Massgabe des Reglements berechnete Leistungen gegenüberzustellen (Schattenrechnung; SZS 2004 S. 576, B 74/03 E. 3.3.3).
3.8 Die bisherige reglementarische Leistung wurde als Teilrente für einen Invaliditätsgrad von 56 % ausgerichtet, welcher eine halbe gesetzliche Invalidenrente gegenüberzustellen war. Neu ist aufgrund des gestiegenen Invaliditätsgrades der Mindestanspruch auf eine obligatorische Vollrente zu wahren. Die Teilrente unterscheidet sich von der Vollrente bloss im Umfang; es handelt sich daher um graduelle Abstufungen eines einzigen Anspruchs, von eigenständigen Leistungsarten wie etwa im Verhältnis von Invaliden- zu Kinderrenten (vgl. <ref-ruling> E. 4.2 S. 577) kann nicht gesprochen werden. In zeitlicher Hinsicht ist der Eintritt der massgeblichen Erhöhung des Invaliditätsgrades ausschlaggebend. Dass sich die reglementarische Leistung auch zu diesem Zeitpunkt aufgrund des bisherigen Invaliditätsgrades von 56 % bemisst (E. 3.5), ist nicht von Belang. Es hat somit eine betragsmässige Anrechnung der (im konkreten Fall unveränderten) reglementarischen Rente an den gesetzlichen Mindestanspruch zu erfolgen. Das Ergebnis entspricht dem gesetzlichen Konzept der überobligatorischen Vorsorge, welches eine weitgehende Gestaltungsfreiheit entsprechender Einrichtungen nicht nur in Bezug auf Invaliditätsbegriff und versichertes Risiko (E. 3.2), sondern auch hinsichtlich weiterer Tatbestände wie Rentenabstufung, versicherte Lohnbestandteile, Teuerungsausgleich (vgl. <ref-ruling>) oder Umwandlungssatz vorsieht. Bei der gegebenen Konstellation ist die Kumulation der bisherigen reglementarischen mit einer neuen obligatorischen Teilrente unzulässig. Soweit aus Urteilen des Eidg. Versicherungsgerichts (etwa SZS 1997 S. 557, B 40/93 E. 5a; SZS 1995 S. 467, B 4/94 E. 5; SZS 2008 S. 363, B 74/06 E. 2.1 in fine mit weiteren Hinweisen) etwas anderes hervorgehen könnte, ist dies hiermit zu präzisieren.
3.9 Die Vorinstanz hat nicht offensichtlich unrichtig und daher für das Bundesgericht verbindlich (E. 1) festgestellt, die überobligatorischen Leistungen für einen Invaliditätsgrad von 56 % seien höher als der obligatorische Anspruch bei einem solchen von 71 %. Nach dem Gesagten hat der Versicherte keinen Anspruch auf eine Erhöhung der Rente. Bei diesem Ergebnis wird die Vorinstanz über die Parteientschädigung für das kantonale Verfahren neu zu befinden haben, wobei u.a. dessen grundsätzliche Kostenfreiheit (Art. 73 Abs. 2 BVG; <ref-ruling> E. 4b S. 150 f.) zu beachten ist.
4. Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten dem Beschwerdegegner aufzuerlegen (<ref-law>).
Die obsiegende Beschwerdeführerin hat keinen Anspruch auf Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, und Dispositiv-Ziffern 1 und 5 des Entscheids des Verwaltungsgerichts des Kantons Bern, Sozialversicherungsrechtliche Abteilung, vom 27. Mai 2009 werden aufgehoben. Die Beschwerdeführerin wird verpflichtet, dem Beschwerdegegner ab 1. November 1998 und über den 1. Januar 2001 hinaus eine Invalidenrente der weitergehenden Vorsorge für einen Invaliditätsgrad von 56 % auszurichten.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdegegner auferlegt.
3. Die Sache wird zur Neuregelung der Parteientschädigung für das vorangegangene Verfahren an das Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, zurückgewiesen.
4. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 19. März 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Dormann