Grundwasserschutz, hat sich ergeben: A.- A.S._ und B.S._ sind Mieter einer ehemaligen Lastwagengarage auf der Parzelle Nr. 444 in Heiden. Die Garage liegt 30 - 40 m von der Grundwasserfassung Bissau-Wies der Dorfbrunnen- und Roosenkorporation Heiden entfernt. Zum Schutze dieser Grundwasserfassung hatte der Regierungsrat des Kantons Appenzell-Ausserrhoden am 15. April 1986 einen Schutzzonenplan mit Schutzreglement erlassen. Danach befindet sich die Parzelle Nr. 444 in der engeren Grundwasserschutzzone S2/b2 (mit beschränkter Schutzwirkung). Die Grundwasserschutzzone S2/b2 wurde am 20. Juni 1986 im Grundbuchblatt der Parzelle Nr. 444 angemerkt. B.- Im Jahre 1993 beabsichtigten A.S._ und B.S._, eine Oldtimer-Trockenwerkstatt in die ursprüngliche Lastwagengarage einzubauen. Gemäss Aussagen von A.S._ und B.S._ habe der Bausekretär des Bauamtes Heiden ihnen im September 1993 die mündliche Zusage gemacht, dass es für ihr Vorhaben keines Baugesuchs bedürfe. Diese Aussage wird vom Bausekretär bestritten. Am 2. Januar 1994 eröffneten A.S._ und B.S._ die gewerbliche Oldtimer-Garage, nachdem sie die bestehende Manngrube geschlossen und dafür zwei moderne Hydrauliklifte sowie, in einer Ecke des Gebäudes, einen separaten Büroraum eingebaut hatten. Im April 1994 wurden sie vom Gemeindebaumeister aufgefordert, nachträglich ein Baugesuch einzureichen. Gegen die nachträgliche Baueingabe vom 11. Mai 1994 (ohne Erwähnung der baulichen Veränderungen) erhob die Dorfbrunnen- und Roosenkorporation (Wasserversorgung) am 4. Juni 1994 Einsprache, weil in der Grundwasserschutzzone S2 keine Autoreparaturwerkstätten zulässig seien. Mit Verfügung vom 1. September 1994 (versandt am 19. April 1995) entschied das kantonale Amt für Umweltschutz, das Baugesuch S._ werde gewässerschutzpolizeilich verweigert. Gestützt darauf hiess die Baubewilligungskommission Heiden am 19. April 1995 die Einsprache der Dorfbrunnen- und Roosenkorporation gut und verweigerte der Trockenwerkstatt die nachträgliche Baubewilligung. C.- A.S._ und B.S._ rekurrierten sowohl gegen die Verweigerung der Baubewilligung (dieses Verfahren ist noch hängig) und gegen die Versagung der gewässerschutzpolizeilichen Bewilligung. Am 21. März 1998 wies die Umweltschutz- und Energiekommission den Rekurs gegen den Entscheid des Umweltschutzamtes ab. D.- Gegen den Rekursentscheid erhoben A.S._ und B.S._ Beschwerde an das Verwaltungsgericht von Appenzell-Ausserrhoden. Dieses führte am 24. Februar 1998 im Beisein der Beteiligten einen Augenschein durch. Am 27. Oktober 1999 wies es die Beschwerde ab. E.- Gegen den am 15. März 2000 zugestellten verwaltungsgerichtlichen Entscheid erhoben A.S._ und B.S._ am 14. April 2000 Verwaltungsgerichtsbeschwerde ans Bundesgericht. Sie beantragen, das angefochtene Urteil sei aufzuheben und die Sache zur Ergänzung des Sachverhalts und zur Neubeurteilung an die Vorinstanz zurückzuweisen. F.- Die Dorfbrunnen- und Roosenkorporation beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Auch das Verwaltungsgericht schliesst auf Beschwerdeabweisung. Der Gemeinderat Heiden und die Umweltschutz- und Energiedirektion haben sich nicht vernehmen lassen. Das Bundesamt für Umwelt, Wald und Landschaft (BUWAL) kommt in seiner Vernehmlassung zum Ergebnis, der angefochtene Entscheid stehe im Einklang mit dem Gewässerschutzrecht des Bundes. Den Beteiligten wurde Gelegenheit gegeben, hierzu Stellung zu nehmen.