Sachverhalt: A. Im Herbst 2001 wurde im Erdgeschoss der Liegenschaft Linsebühlstrasse 82 in St. Gallen (Grundstück Nr. C1282), dem ehemaligen Hotel Walfisch und späteren Durchgangszentrum für Asylbewerber, eine Gassenküche errichtet. Das Grundstück liegt in der Wohn-Gewerbe-Zone. In den ersten beiden Obergeschossen wurden Büros und Arbeitsräume eingerichtet. Eigentümerin ist die Politische Gemeinde St. Gallen. Betreiberin der Gassenküche ist die Stiftung Suchthilfe, die vom Kanton und der Stadt St. Gallen sowie von kirchlichen und sozialen Organisationen getragen wird. Bereits vor Eröffnung der Gassenküche hatten die Ehegatten X._, die Eigentümer des südwestlich angrenzenden Grundstücks Nr. C1283 mit Bäckerei an der Linsebühlstrasse 80, die Bauverwaltung der Stadt St. Gallen aufgefordert, umgehend ein Baubewilligungsverfahren einzuleiten. Die Baupolizei der Stadt St. Gallen traf am 12. Juli 2001 eine Feststellungsverfügung, wonach die Nutzung der Liegenschaft Linsebühlstrasse 82 als Gassenküche nicht als Zweckänderung im Sinne des Baurechts gelte und für die inneren Umbauarbeiten das abgekürzte Baugesuchsverfahren durchgeführt worden sei. Gegen diese Feststellungsverfügung erhoben die Ehegatten X._ Rekurs. Das Baudepartement hiess diesen mit Entscheid vom 4. Juni 2002 gut und hob die angefochtene Verfügung auf. Es hielt fest, eine Zweckänderung der Liegenschaft könne nicht ausgeschlossen werden, und auch die mit dem Betrieb verbundenen ideellen Immissionen würden eine Überprüfung im Baubewilligungsverfahren rechtfertigen. Das Verwaltungsgericht trat mit Urteil vom 6. Dezember 2002 auf die von der Baupolizei gegen den Rekursentscheid erhobene Beschwerde nicht ein, da kein Beschluss des Stadtrates über die Anfechtung vorlag. B. Das Hochbauamt der Stadt St. Gallen stellte am 17. März 2003 ein Baugesuch für die nachträgliche Bewilligung der Umnutzung des Erdgeschosses der Liegenschaft Linsebühlstrasse 82 in eine Gassenküche. Gegen das Baugesuch erhoben unter anderem die Ehegatten X._ Einsprache. Im Einspracheverfahren versuchte die Baupolizeikommission, mit den Einsprechern und der Betreiberin der Gassenküche mittels einer Anpassung des Betriebskonzepts und geeigneter Auflagen eine Verständigung zu erreichen, was jedoch nicht gelang. Mit Entscheid vom 21. Juli 2006 erteilte die Baupolizeikommission der Stadt St. Gallen die Baubewilligung unter Vorbehalt von Bedingungen und Auflagen. Unter Ziff. IV.3 der Baubewilligung wurde folgendes festgehalten: "Gemäss den Erwägungen unter III./5.32 hat die Grundeigentümerin an allen Öffnungszeiten der Gassenküche folgende Massnahmen sicher zu stellen und mittels Mietvertrag der jeweiligen Betreiberin der Gassenküche zu überbinden: Die tägliche Öffnungszeit der Gassenküche für die Klientschaft wird auf die Zeit zwischen 11.00 Uhr und 17.00 Uhr beschränkt. Ausserhalb der täglichen Öffnungszeit muss die Gassenküche für die Klientschaft geschlossen bleiben. An allen Öffnungszeiten müssen während der ganzen täglichen Öffnungszeit mindestens zwei Betreuungspersonen anwesend und für die Klientschaft ansprechbar sein. An allen Öffnungszeiten ist die Umgebung innerhalb eines Umkreises von 150 m in den Strassenzügen Linsebühlstrasse - Sägegässchen - Konkordiastrasse - Sternackerstrasse - Schwalbenstrasse - Axensteinstrasse - Speicherweg - Speicherstrasse durch eine Betreuungsperson in Bezug auf die Klientschaft der Gassenküche zu beobachten. Im Zusammenhang mit der Beobachtung der bezeichneten Umgebung sind dem Amt für Baubewilligungen sowie der Grundeigentümerin die Telefonnummern des Leiters der Gassenküche bzw., bei dessen Abwesenheit, des Leiters der Stiftung Suchthilfe als Kontaktperson bekannt zu geben. Die Beobachtung der bezeichneten Umgebung hat an allen Öffnungstagen mindestens viermal, d.h. vor der Eröffnung, während des Betriebs sowie nach Betriebsschluss zu erfolgen. Ein besonderes Augenmerk ist dabei auf die Innenhöfe zu richten. Der Zugang der Gassenküche darf für die Klientschaft nur durch den Eingang an der Linsebühlstrasse erfolgen. Die Hintertüre im hofseitigen Bereich ist für die Klientschaft geschlossen zu halten. Allfällige Anpassungen des Betriebs- und Betreuungskonzeptes, welche Auswirkungen auf die Umgebung oder eine Vergrösserung des Benützerkreises zur Folge haben (Ausdehnung Öffnungszeiten, Erweiterung Angebot, etc.), unterliegen gemäss Art. 78 Abs. 2 lit. o BauG der vorgängigen Bewilligungspflicht. Allfällige Konzeptanpassungen sind vorgängig mit dem Amt für Baubewilligungen auf ihre Bewilligungspflicht zu überprüfen." Die Baupolizeikommission hielt fest, aufgrund der vor rund sechs Jahren beendeten inneren Umbauarbeiten sei lediglich die Umnutzung zu beurteilen. Die Zweckänderung werde bejaht. Zielpublikum einer Gassenküche seien drogenabhängige und alkoholsüchtige Personen, weshalb die Auswirkungen des Betriebs nicht mit jenen eines Durchgangszentrums für Asylbewerber verglichen werden könnten. Zu bejahen sei auch die Zonenkonformität. Die verfügten Auflagen hätten sich während der Betriebsdauer der Gassenküche am alten Standort bewährt. Damit könnten ein ordentlicher Betrieb sichergestellt und allfällige Immissionen auf ein zulässiges Mass herabgesetzt werden. C. Die Ehegatten X._ beantragten mit Rekurs beim Baudepartement des Kantons St. Gallen, der Beschluss der Baupolizeikommission sei vollumfänglich aufzuheben und die Bewilligung für die Umnutzung des Erdgeschosses der Liegenschaft Linsebühlstrasse 82 von einem Restaurant in die Gassenküche sei zu verweigern. Der Betrieb einer Gassenküche werde zwar grundsätzlich befürwortet. Die Einwirkungen auf die Nachbarschaft müssten jedoch mittels Auflagen und Bedingungen auf ein vertretbares Mass gebracht werden. Aufgrund der unmittelbaren räumlichen Nähe der Gassenküche zum Bäckereibetrieb werde der Schutz der Nachbarschaft nicht gewährleistet. Dementsprechend würden verschiedene zusätzliche Auflagen beantragt. Das Baudepartement hiess den Rekurs mit Entschied am 9. Juni 2008 teilweise gut. In Ziff. 2 seines Entscheids hob es Ziff. IV.3 des Beschlusses der Baupolizeikommission vom 21. Juli 2006 auf und ersetzte die darin enthaltenen Anordnungen durch folgende Bestimmungen: "Die Grundeigentümerin hat an allen Öffnungstagen der Gassenküche folgende Massnahmen sicher zu stellen und mittels Mietvertrag der jeweiligen Betreiberin der Gassenküche zu überbinden: a) Die tägliche Öffnungszeit der Gassenküche für die Klientschaft wird auf die Zeit zwischen 11.00 Uhr und 17.00 Uhr beschränkt. Ausserhalb der täglichen Öffnungszeit muss die Gassenküche für die Klienten geschlossen bleiben. b) An allen Öffnungstagen müssen während der ganzen täglichen Öffnungszeiten mindestens drei Betreuungspersonen (festangestelltes ausgebildetes Personal) anwesend und für die Klientschaft ansprechbar sein. c) An allen Öffnungstagen ist die Umgebung innerhalb eines Umkreises von 150 m um die Gassenküche in den Strassenzügen Linsebühlstrasse - Sägegässchen - Konkordiastrasse - Sternackerstrasse - Schwalbenstrasse - Axensteinstrasse - Speicherweg - Speicherstrasse durch mindestens eine Betreuungsperson in Bezug auf die Klientschaft der Gassenküche zu überwachen. d) Die für die Überwachung der bezeichneten Umgebung zuständige Betreuungsperson ist dem Amt für Baubewilligungen sowie den Grundeigentümern im Gebiet innerhalb der Strassenzüge Linsebühlstrasse - Sägegässchen - Konkordiastrasse - Sternackerstrasse - Schwalbenstrasse - Axensteinstrasse - Speicherweg - Speicherstrasse unter Angabe einer Telefonnummer als Kontaktperson im Voraus und rechtzeitig bekannt zu geben. e) Die Überwachung der bezeichneten Umgebung hat an allen Öffnungstagen mindestens im folgenden Umfang zu erfolgen: aa) Ab spätestens 10.45 Uhr bis 11.00 Uhr ist ein Kontrollgang durch die bezeichnete Umgebung mit besonderem Augenmerk auf die Innenhöfe sowie auf die der Gassenküche zuführenden Wege durchzuführen. bb) Während 11.00 Uhr bis 17.00 Uhr ist mindestens ein Kontrollgang durch die bezeichnete Umgebung mit besonderem Augenmerk auf die Innenhöfe durchzuführen. cc) Ab 17.00 Uhr bis mindestens 17.15 Uhr ist ein Kontrollgang durch die bezeichnete Umgebung mit besonderem Augenmerk auf die Innenhöfe sowie auf die von der Gassenküche wegführenden Wege durchzuführen. f) Während der Kontrollgänge in der bezeichneten Umgebung ist ein Fehlverhalten der Klientschaft der Gassenküche zu verhindern oder zumindest umgehend deren Folgen zu beseitigen. g) Die durchgeführten Kontrollgänge (unter Angabe der Zeit) sowie allfälliges Fehlverhalten der Klientschaft der Gassenküche sind zu protokollieren. Das durch die für die Überwachung der Umgebung zuständige Betreuungsperson zu unterzeichnende Protokoll ist jeweils am Ende eines Kalendermonats dem Amt für Baubewilligungen zuzustellen. Die Grundeigentümer im Gebiet innerhalb der Strassenzüge Linsebühlstrasse - Sägegässchen - Konkordiastrasse - Sternackerstrasse - Schwalbenstrasse - Axensteinstrasse - Speicherweg - Speicherstrasse können beim Amt für Baubewilligungen in das Protokoll Einsicht nehmen. h) Durch die Klientschaft der Gassenküche in der Gassenküche oder in der bezeichneten Umgebung begangene Straftaten sind an allen Öffnungstagen durch eine der anwesenden Betreuungspersonen ohne Verzug der Stadtpolizei anzuzeigen. i) An allen Öffnungstagen sind innerhalb der Gassenküche oder in der bezeichneten Umgebung festgestelltes Fehlverhalten oder begangene Straftaten durch die Klientschaft je nach Schweregrad durch eine der anwesenden Betreuungspersonen mit einem zeitlich beschränkten Zutrittsverbot in die Gassenküche von einem bis sieben Tagen zu ahnden. Im Wiederholungsfall ist ein zeitlich unbeschränktes Zutrittsverbot zu erlassen. k) Der Zugang zur Gassenküche darf für die Klientschaft der Gassenküche nur durch den Eingang an der Linsebühlstrasse erfolgen. Die Hintertüre im hofseitigen Bereich steht nur den Betreuungspersonen offen und ist für die Klientschaft geschlossen zu halten." In Ziff. 4 seines Entscheids verpflichtete das Baudepartement die Politische Gemeinde St. Gallen, die Rekurrenten ausseramtlich mit Fr. 2'500.-- zuzüglich Mehrwertsteuer und Barauslagen von Fr. 165.-- zu entschädigen. D. Gegen den Rekursentscheid des Baudepartements erhob die Politische Gemeinde St. Gallen Beschwerde beim Verwaltungsgericht des Kantons St. Gallen. Sie beantragte, der Rekursentscheid sei aufzuheben und die im Beschluss der Baupolizeikommission vom 21. Juli 2006 enthaltene Bestimmung Ziff. IV.3 sei zu bestätigen. Die Beschwerde des Stadtrats richtete sich gegen die Verschärfung der im Beschluss der Baupolizeikommission verfügten Bedingungen und Auflagen. Die vom Baudepartement vorgenommene Verschärfung der in der Baubewilligung enthaltenen Auflagen sei nicht nötig und somit unverhältnismässig. Sie enthalte eine krasse Überregulierung, die teilweise mit der sozialen Aufgabe der Gassenküche unvereinbar sei. Das Verwaltungsgericht hiess die Beschwerde mit Urteil vom 22. Januar 2009 gut, soweit es darauf eintrat, und hob Ziff. 2 und 4 des Rekursentscheids des Baudepartements vom 9. Juni 2008 auf. Es gelangte zum Schluss, dass die vom Baudepartement angeordneten zusätzlichen Vorschriften für den Betrieb der Gassenküche mit dem Verhältnismässigkeitsprinzip nicht vereinbar seien. E. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. März 2009 beantragen die Ehegatten X._ im Wesentlichen, das Urteil des Verwaltungsgerichts vom 22. Januar 2009 sei aufzuheben und der Rekursentscheid des Baudepartements vom 9. Juni 2008 zu bestätigen. Sie rügen in mehrfacher Hinsicht die Verletzung des Willkürverbots (Art. 9 BV) und des Anspruchs auf rechtliches Gehör (Art. 29 Abs. 2 BV), beanstanden eine offensichtlich unrichtige Sachverhaltsermittlung im Sinne von Art. 97 Abs. 1 BGG und machen die Missachtung von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV) sowie des Verhältnismässigkeitsprinzips (Art. 5 Abs. 2 BV) geltend. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde. Das Baudepartement verzichtet unter Verweisung auf seinen Entscheid vom 9. Juni 2008 auf eine Vernehmlassung. Die Stadt St. Gallen stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne.