Sachverhalt: A. Mit Beschluss vom 8. November 2005 verweigerte die Bausektion der Stadt Zürich die nachträgliche baurechtliche Bewilligung für die sexgewerbliche Nutzung der Lokalitäten im Untergeschoss, Erdgeschoss sowie 1. und 4. Obergeschoss der im Eigentum der Rehe AG stehenden Liegenschaft Dienerstrasse 2 in Zürich (Grundstück Kat.-Nr. AU 4882). A._, B._, C._ und weiteren namentlich genannten Personen als Mieterschaften sowie allen Rechtsnachfolgerinnen und -nachfolgern wurde befohlen, bis spätestens drei Monate ab Rechtskraft des Entscheids die sexgewerbliche Nutzung der von ihnen gemieteten Räume zu beenden, die Lokalitäten zu räumen und dafür besorgt zu sein, dass allfällige sich darin befindliche Drittpersonen, insbesondere Prostituierte, die Räume verlassen. Nachdem dieser Entscheid in Rechtskraft erwachsen war, forderte das Hochbaudepartement der Stadt Zürich die Rehe AG mit Schreiben vom 20. April 2007 auf, sämtliche betroffenen Mietverhältnisse aufzulösen und die fraglichen Lokalitäten zu räumen. Darauf stellten A._, B._, C._ sowie die D._ GmbH am 27. Mai 2007 ein Wiedererwägungs- und Revisionsgesuch wegen behaupteter Entdeckung von Verfahrensmängeln. Die Bausektion der Stadt Zürich trat mit Beschluss vom 10. Juli 2007 auf das Gesuch nicht ein. B. Gegen den Beschluss vom 10. Juli 2007 reichten A._, B._, C._ sowie die D._ GmbH Rekurs bei der Baurekurskommission des Kantons Zürich ein und verlangten die Aufhebung des Nichteintretensentscheids. Mit Entscheid vom 13. März 2008 wies die Baurekurskommission den Rekurs ab. In der Folge erhoben A._, B._, C._ sowie die D._ GmbH Beschwerde beim Verwaltungsgericht des Kantons Zürich. Sie beantragten die Aufhebung des angefochtenen Entscheids; eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Mit Entscheid vom 20. August 2008 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, der Bauentscheid vom 8. November 2005 sei mit einer korrekten Rechtsmittelbelehrung zugestellt worden. Damit seien die betroffenen Mieter in das Verfahren einbezogen worden, weshalb kein Revisionsgrund vorliege. C. Mit Eingabe vom 7. Oktober 2008 erheben A._, B._, C._ sowie die D._ GmbH beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG). Sie beantragen die Feststellung des Vorliegens eines Revisionsgrundes, die Aufhebung des verwaltungsgerichtlichen Entscheids vom 20. August 2008 und die Rückweisung der Sache zur Neubeurteilung an die Vorinstanz. Sie rügen eine Verletzung der Verfahrensgarantien gemäss Art. 18 Abs. 2 KV/ZH (SR 131.211) sowie der Grundsätze rechtsstaatlichen Handelns (Art. 5 BV), der Rechtsgleichheit (Art. 8 BV), des Willkürverbots und des Grundsatzes von Treu und Glauben (Art. 9 BV) sowie ihres Anspruchs auf ein gerechtes Verfahren und auf rechtliches Gehör (Art. 29 Abs. 1 und 2 BV). D. Das Verwaltungsgericht und die Bausektion der Stadt Zürich schliessen in ihren Vernehmlassungen auf Abweisung der Beschwerde. Die Beschwerdeführer haben von der Gelegenheit eine Replik einzureichen Gebrauch gemacht. Mit Eingabe vom 19. Januar 2009 halten sie an ihren bisherigen Ausführungen und Anträgen fest.