Sachverhalt:
A. Mit Urteil vom 16. Januar 2003 (1P.343 - 346/2002) hiess das Bundesgericht vier staatsrechtliche Beschwerden betreffend den dritten Teilzonenplan Ifang, Herisau, im Sinne der Erwägungen teilweise gut und hob das Urteil des Verwaltungsgerichts von Appenzell Ausserrhoden vom 25. Oktober 2000/20. März 2002 insoweit auf, als darin die Parzelle Nr. 1813 und die Teilfläche von Parzelle Nr. 1794 entlang der Staatsstrasse (eine Bautiefe) dem übrigen Gemeindegebiet zugewiesen wurden. Das Bundesgericht vertrat die Auffassung, in Bezug auf diese Parzellen(teile) sei es vertretbar, von einer Baulücke zu sprechen, weshalb die Zuweisung zum übrigen Gemeindegebiet nicht die einzige mögliche planerische Lösung sei. Unter diesen Umständen habe das Verwaltungsgericht die Gemeindeautonomie verletzt, indem es auf eine Rückweisung verzichtete, die der Gemeinde die Einzonung der erwähnten Flächen gestattet hätte, und statt dessen einen eigenen Planungsentscheid traf.
Mit Urteil vom 21. Mai 2003 wies das Verwaltungsgericht die Sache im Umfang der Parzelle Nr. 1813 und der Teilfläche auf Parzelle Nr. 1794 an die Gemeinde Herisau zurück, damit diese über deren Zuweisung ins übrige Gemeindegebiet oder in eine Bauzone (Wohnzone) im Rahmen eines öffentlich aufzulegenden Teilzonenplanes neu befinde.
B. Am 25. Januar 2005 beschloss der Gemeinderat Herisau den vierten Teilzonenplan Ifang und legte diesen öffentlich auf. Danach sollen eine Fläche im Halte von rund 700 m2 auf Parzelle Nr. 1794 der Wohnzone W3 und der überwiegende Teil der Parzelle Nr. 1813 (ohne Teilfläche im Wald und im Waldabstand) der Wohnzone W2 zugewiesen werden.
Dagegen erhoben X._ und A._ als Eigentümer der angrenzenden Parzellen (Nrn. 2066/3072 und 2070) Einsprache mit dem Begehren, die Parzelle Nr. 1813 sei dem übrigen Gemeindegebiet zuzuweisen. Am 16. August 2005 wies der Gemeinderat Herisau die Einsprache ab, soweit er darauf eintrat. Am 7. Dezember 2005 genehmigte der Einwohnerrat von Herisau den vierten Teilzonenplan Ifang ohne Änderung. Am 9. Januar 2005 lief die Referendumsfrist ungenutzt ab.
C. Gegen den Einspracheentscheid erhoben X._ und A._ gemeinsam Rekurs an den Regierungsrat des Kantons Appenzell Ausserrhoden. Dieser wies den Rekurs am 19. Dezember 2006 ab und genehmigte gleichentags den vierten Teilzonenplan Ifang mit der Einschränkung, dass die Gewässerabstandsfläche auf Parzelle Nr. 1813 der Grünzone zuzuweisen sei.
D. Gegen den Rekursentscheid erhoben X._ und A._ gemeinsam Beschwerde ans Verwaltungsgericht.
Dieses führte am 28. November 2007 einen Augenschein durch. Es stellte fest, dass auf der nordöstlichen Grenze der Parzelle Nr. 1813, auf dem Kamm des zur Staatsstrasse abfallenden Hügels, eine Hecke steht, die eine natürliche Grenze zwischen der Reihenhausüberbauung und der noch unüberbauten Parzelle Nr. 1813 markiere. Gegen Südwesten trete die Parzelle 1813 zusammen mit der angrenzenden Parzelle 3713 als eine unüberbaute, noch landwirtschaftliche genutzte Wiesenmulde in Erscheinung, welche auf der Höhe der erwähnten Hecke und nicht schon am eingedolten Bachlauf ende. Die noch unüberbaute Parzelle 1813 habe an der Siedlungsqualität der auf dem Hügelkamm und damit deutlich höher gelegenen Reihenhausbaute nicht teil. Unter den an Ort tatsächlich gegebenen Umständen erscheine die Bezeichnung der peripher gelegenen Parzelle Nr. 1813 als Baulücke oder sonst als Teil des weitgehend überbauten Gebiets insgesamt als nicht haltbar. Die Parzelle sei weit eher der nach Südosten und Norden hin offenen Landschaft zuzurechnen. Eine Offenlegung des seit langem eingedolten Bachlaufes würde den naturnahen Charakter der Parzelle 1813 noch verstärken. Das nordwestlich angrenzende Waldgeviert lasse die Parzelle bestenfalls auf dem Plan, nicht aber vor Ort als Endpunkt einer aufzufüllenden Baulücke erscheinen.
Das Verwaltungsgericht hielt sich allerdings an den Bundesgerichtsentscheid vom 16. Januar 2003 gebunden, der verbindlich festgestellt habe, dass es sich bei der Parzelle Nr. 1813 um eine Baulücke handle. Aus diesem Grund sei nicht zu beanstanden, dass die Gemeinde Herisau das Grundstück als weitgehend überbautes Land i.S.v. Art. 15 lit. a RPG der Bauzone zugewiesen habe. Das Verwaltungsgericht wies deshalb die Beschwerde ab.
E. Gegen den verwaltungsgerichtlichen Entscheid, der ihm am 15. Oktober 2008 zugestellt worden war, hat X._ am 14. November 2008 Beschwerde ans Bundesgericht erhoben. Er beantragt die Aufhebung des angefochtenen Entscheids. Eventualiter sei aufgrund des missbräuchlich angeordneten Augenscheins die Gerichtsgebühr massiv zu kürzen und ein Teil der Entschädigung an die Y._ AG der öffentlichen Hand anzulasten.
F. Die Y._ AG und das Departement Bau und Umwelt schliessen auf Abweisung der Beschwerde. Die Gemeinde Herisau beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht hat auf einen Antrag verzichtet.
G. In der Replik hält der Beschwerdeführer an seinen Anträgen fest.

Erwägungen:
1. Angefochten ist der kantonal letztinstanzliche Entscheid über den 4. Teilzonenplan Ifang. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen. Da alle Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde in diesem Verfahren einzutreten.
2. Der Beschwerdeführer macht geltend, das Verwaltungsgericht habe sich zu Unrecht an das Urteil des Bundesgerichts gebunden gefühlt. Er vertritt die Auffassung, das neu eröffnete Einspracheverfahren habe auf den Inhalt der früheren Entscheide keine Rücksicht nehmen müssen, zumal sich zwischenzeitlich die personelle Besetzung der Behörden und Gerichte geändert habe und es sich um eine ausgesprochene Ermessensfrage handle. Die Rückweisung sei nur insoweit bindend gewesen, als die Frage des Vorliegens einer Baulücke nochmals eingehend habe geprüft werden müssen. Das Bundesgericht, das keinen eigenen Augenschein durchgeführt habe, habe die Parzelle Nr. 1813 nicht verbindlich als Baulücke einstufen, sondern lediglich die Existenz einer Baulücke nicht ausschliessen können. Die Rückweisung sei erfolgt, um die strittige Parzelle entweder einer Wohnzone oder dem übrigen Gemeindegebiet zuzuweisen; damit sei der Ausgang des Planungsverfahrens gerade nicht verbindlich vorgegeben gewesen. Unter diesen Umständen verstosse der verwaltungsgerichtliche Entscheid auch gegen Treu und Glauben, weil für potentielle Einsprecher der Eindruck entstanden sei, dass im neuen Planungsverfahren frei über die Zuordnung der Parzelle zum übrigen Gemeindegebiet entschieden werden könne.
2.1 Der bundesgerichtliche Entscheid, dessen Bindungswirkung streitig ist, erging im Verfahren der staatsrechtlichen Beschwerde gemäss OG, und nicht nach dem (heute geltenden) BGG. Damit beurteilt sich seine Bindungswirkung nach den damals geltenden prozessualen Grundsätzen des Bundesrechts. Diese prüft das Bundesgericht mit freier Kognition (Entscheid 4P.244/2005 vom 6. Februar 2006, in: Pra 2007 Nr. 8 S. 40, E. 3.3).
2.2 Der in den Art. 66 Abs. 1 OG und Art. 277ter Abs. 2 BStP niedergelegte Grundsatz, wonach die kantonale Instanz im Rückweisungsverfahren ihrer Entscheidung die rechtliche Begründung des Bundesgerichts zugrunde zu legen hat, galt grundsätzlich auch für das staatsrechtliche Verfahren: Gemäss ständiger bundesgerichtlicher Rechtsprechung grenzten die Motive des staatsrechtlichen Urteils den Gegenstand des Prozesses endgültig ab und waren insoweit sowohl für die kantonalen Richter, an die zurückgewiesen wurde, wie auch für das Bundesgericht selbst, bindend (<ref-ruling> E. 1 S. 63; <ref-ruling> E. 2 S. 30). Die kantonale Instanz, deren Entscheid auf staatsrechtliche Beschwerde hin aufgehoben wurde, musste sich an die Erwägungen des bundesgerichtlichen Urteils halten und durfte ihren neuen Entscheid nicht auf Erwägungen stützen, die das Bundesgericht ausdrücklich oder sinngemäss verworfen hatte (<ref-ruling> E. 3c/bb S. 354; <ref-ruling> E. 2 S. 95 mit Hinweisen).
Diese Bindungswirkung wurde allerdings aufgrund der Natur der staatsrechtlichen Beschwerde in bestimmtem Ausmass eingeschränkt. Zum einen überprüfte das Bundesgericht in der Regel den kantonalen Entscheid lediglich auf der Grundlage der im Beschwerdeverfahren erhobenen Rügen und beschränkte sich im Allgemeinen auf die Aufhebung des Entscheides, womit die gerügte Verfassungsverletzung behoben war. Das Urteil des Bundesgerichts trat in diesen Fällen nicht an die Stelle des aufgehobenen kantonalen Entscheides. Zum andern griff das Bundesgericht in der Regel bloss ein, wenn der kantonale Entscheid nicht nur durch seine Begründung, sondern auch im Ergebnis die Verfassung verletzte. Das gab dem Bundesgericht die Möglichkeit, die verfassungswidrige Begründung des angefochtenen Entscheides durch eine verfassungskonforme zu ersetzen. Hatte es jedoch auf eine solche Substitution der Motive verzichtet, konnte das kantonale Gericht nach der Rückweisung selbst so vorgehen, soweit das Bundesgericht nicht bereits bestimmte Urteilsgründe im Rückweisungsentscheid ausdrücklich oder implizit verworfen hatte (<ref-ruling> E. 3c/bb S. 355; Urteil 4P.244/2005 vom 6. Februar 2006, in: Pra 2007 Nr. 8 S. 40, E. 1.2; Urteil 4A.5/2008 vom 22. Mai 2008 E. 1.2).
2.3 Im vorliegenden Fall sprach das Bundesgericht zwar keine förmliche Rückweisung der Sache an das Verwaltungsgericht aus; es hiess jedoch die Beschwerden "im Sinne der Erwägungen" gut und machte damit die Erwägungen zum integralen Bestandteil des Dispositivs (BGE 98 I 64 E. 2a S. 69). Dies gilt jedenfalls für diejenigen Erwägungen, die das weitere Vorgehen der Behörden in der Sache betreffen und deshalb auch (in Form einer Rückweisung oder einer positiven Anordnung) Teil des Dispositivs hätten sein können (vgl. PHILIPPE GERBER, La nature cassatoire du recours de droit public, Diss. Genf 1997, S. 205).
2.4 Massgeblich ist im vorliegenden Fall E. 9 des Urteils vom 16. Januar 2003. Darin hiess das Bundesgericht die Rüge der Verletzung der Gemeindeautonomie gut, soweit das Verwaltungsgericht auch die Parzellen Nrn. 1813 und 1794 dem übrigen Gemeindegebiet zugeteilt hatte. Das Bundesgericht ging davon aus, dass diese Parzellen vollständig erschlossen seien; zudem lasse es sich bei beiden Parzellen vertreten, von einer Baulücke zu sprechen, weshalb die Zuweisung zum übrigen Gemeindegebiet nicht die einzig mögliche Lösung sei. Unter diesen Umständen habe das Verwaltungsgericht die Gemeindeautonomie insofern verletzt, als es auf eine Rückweisung verzichtete, die der Gemeinde die Einzonung der erwähnten Flächen gestattet hätte, und statt dessen den Planungsentscheid selbst traf.
2.4.1 Aus dieser Erwägung ergibt sich zunächst, dass die Sache zu neuem Entscheid an die Gemeinde zurückgewiesen werden muss; insofern rechtfertigt es sich, das bundesgerichtliche Urteil einem Rückweisungsentscheid gleichzustellen.
2.4.2 Das Bundesgericht hielt das Vorliegen einer Baulücke bei der Teilfläche von Parzelle Nr. 1794 für offensichtlich. Zur Parzelle Nr. 1813 führte es Folgendes aus: Zwar handle es sich um ein Grundstück am Ende der die Kantonsstrasse säumenden Bebauung; ein landschaftlich überzeugender Abschluss der Bauzeile werde indessen erst durch das Wäldchen hinter der Parzelle Nr. 1813 gebildet. Es hielt es daher bei beiden Parzellen für vertretbar, von einer Baulücke zu sprechen.
Damit entschied das Bundesgericht, dass es im planerischen Ermessen der Gemeinde liege, die fraglichen Parzellen als Baulücke zu qualifizieren. An diese Beurteilung war das Verwaltungsgericht gebunden. Es durfte deshalb die Zuweisung der Parzelle Nr. 1813 zur Wohnzone nicht mit der Begründung aufheben, es liege - entgegen der Auffassung der Gemeinde - keine Baulücke vor.
2.5 Es ist nicht ersichtlich, inwiefern dies dem Grundsatz von Treu und Glauben widerspricht. Die Durchführung eines öffentlichen Auflage- und Einspracheverfahrens trug dem Umstand Rechnung, dass die Gemeinde noch ein gewisses Planungsermessen hatte und sich noch gegen die Zuweisung der Parzellen zur Bauzone hätte entscheiden können (vgl. unten E. 3).
3. Weitgehend überbautes Land ist gemäss Art. 15 lit. a RPG in der Regel in die Bauzone einzubeziehen. Vorbehalten bleiben Fälle, in denen sich als Folge der Abwägung aller für die Raumplanung massgebenden Zielsetzungen die Zuweisung in eine Nichtbauzone aufdrängt (BERNHARD WALDMANN/PETER HÄNNI, Handkommentar RPG, Art. 15 Rz 26). Zu dieser Frage hat sich der Bundesgerichtsentscheid vom 16. Januar 2003 nicht geäussert. Sowohl die Gemeinde als auch das Verwaltungsgericht kamen jedoch zum Ergebnis, dass keine überwiegenden Gründe ersichtlich seien, die Parzelle Nr. 1813 trotz ihrer Qualifikation als Baulücke einer Nichtbauzone zuzuweisen.
3.1 Der Beschwerdeführer macht in diesem Zusammenhang geltend, bei der Überbauung der Parzelle Nr. 1813 müsse er eine massive Beschattung seines Gemüsegartens in Kauf nehmen. Zudem sei der Waldabstand für die Parzelle Nr. 1813 willkürlich herabgesetzt worden; nur aus diesem Grund sei die Parzelle überhaupt überbaubar. Auf diese Fragen seien die kantonalen Behörden nicht eingegangen; dies stelle eine Verweigerung des rechtlichen Gehörs dar.
3.1.1 Der Regierungsrat hatte im Rekursentscheid ausgeführt, für die Wohnzone W2 gelte ein kleiner Grenzabstand von 5 m und ein grosser Grenzabstand von 8 m sowie eine maximale Gebäudehöhe von 7.5 m und eine maximale Firsthöhe von 11.5 m; es sei nicht ersichtlich, dass die Anwendung dieser Vorschiften im interessierenden Bereich zu einer übermässigen, mit RPG und Baugesetz nicht mehr zu vereinbarenden, Beeinträchtigung der Nachbargrundstücke führen werde. Zudem sei die Parzelle Nr. 1813 von den Parzellen der Beschwerdeführer zur Staatsstrasse hin abfallend. Diese Auffassung vertrat auch das Verwaltungsgericht: Die befürchtete Beschattung werde durch die vorgeschriebenen Grenzabstände und das zur Mulde hin abfallende Gelände gemildert.
3.1.2 Auf die Rüge, der Waldabstand sei willkürlich von 20 auf 12 m verringert worden, trat die Gemeinde Herisau in ihrem Einspracheentscheid nicht ein, weil der reduzierte Waldabstand gemäss Art. 113 des kantonales Gesetzes über die Raumplanung und das Baurecht vom 12. Mai 2003 (BauG) bereits im dritten Teilzonenplan Ifang rechtsverbindlich in Form einer Baulinie festgesetzt worden sei. Dies bestätigte auch der Regierungsrat. In der Beschwerde an das Verwaltungsgericht machte der Beschwerdeführer hinsichtlich des Waldes nur noch geltend, ihm drohe (als Eigentümer der Waldparzelle) die Haftpflicht für auf ein künftiges Gebäude stürzende Bäume. Mit dieser Rüge befasste sich das Verwaltungsgericht und führte aus, der befürchteten Gefährdung durch umstürzende Bäume werde durch die vorgeschriebene Einhaltung eines Waldabstands begegnet.
3.1.3 Danach haben sich die kantonalen Instanzen mit den jeweiligen Rügen des Beschwerdeführers betreffend Beschattung und Waldabstand auseinandergesetzt, weshalb sich die Rüge der Verletzung des rechtlichen Gehörs als unbegründet erweist. Der Beschwerdeführer legt nicht dar, inwiefern die Erwägungen der Behörden und das Verwaltungsgericht auf offensichtlich falschen Sachverhaltsfeststellungen beruhen oder Bundesrecht verletzen.
3.2 Schliesslich macht der Beschwerdeführer geltend, die Parzelle Nr. 1813 eigne sich aufgrund des vom Regierungsrat festgelegten Gewässerabstands nicht für eine Überbauung. Weshalb dem so sei, wird jedoch vom Beschwerdeführer weder dargelegt noch ergibt sich dies aus den Akten.
4. Der Beschwerdeführer macht schliesslich geltend, dass es angesichts der Bindung des Verwaltungsgerichts an den bundesgerichtlichen Entscheid überflüssig gewesen sei, einen Augenschein durchzuführen. Es sei daher willkürlich, ihm die Kosten dieses Augenscheins aufzuerlegen.
4.1 Das Verwaltungsgericht stützte den Kostenentscheid auf Art. 53 Abs. 1 und 3 i.V.m. Art. 19 des Gesetzes über die Verwaltungsrechtspflege vom 9. September 2002 (VRPG) sowie Art. 4a des Gesetzes über die Gebühren in Verwaltungssachen vom 25. April 1982 (GGV). Danach trägt grundsätzlich derjenige die Kosten, der eine Amtshandlung verlangt oder veranlasst (Art. 19 Abs. 1 VRPG); in Rechtsmittelverfahren ist gebühren- und kostenpflichtig, wer ganz oder teilweise unterliegt (Art. 19 Abs. 3 VRPG).
4.2 Das Verwaltungsgericht ging davon aus, der Beschwerdeführer habe eine ungenügende Feststellung des Sachverhalts durch die Vorinstanz und auch durch das Bundesgericht gerügt, weshalb das Verwaltungsgericht zu einem Augenschein habe laden müssen.
Diese Ausführungen lassen keine Willkür erkennen. Zwar hat der Beschwerdeführer den Augenschein nicht ausdrücklich beantragt; er erhob jedoch zahlreiche Sachverhaltsrügen und warf dem Regierungsrat vor, keinen eigenen Augenschein durchgeführt zu haben. Insofern hat er den Augenschein des Verwaltungsgerichts veranlasst.
Zudem erfolgte die Vorladung zum Augenschein durch den Gerichtsschreiber am 17. September 2007, zu einem Zeitpunkt, als das Verwaltungsgericht noch nicht über den Umfang seiner Bindung an den bundesgerichtlichen Rückweisungsentscheid entschieden hatte. Zu diesem Zeitpunkt stand deshalb noch nicht fest, dass der Augenschein überflüssig sei.
5. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten und muss die private Beschwerdegegnerin entschädigen (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Y._ AG für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde Herisau, dem Regierungsrat und dem Verwaltungsgericht von Appenzell Ausserrhoden, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 18. März 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber