Sachverhalt:
A. Rechtsanwalt E._ gelangte am 3. Januar 2007 an die Aufsichtskommission über die Anwältinnen und Anwälte im Kanton Zürich, um zwecks Geltendmachung einer offenen Honorarforderung vom Anwaltsgeheimnis entbunden zu werden. Mit Beschluss vom 1. Februar 2007 gab die Aufsichtskommission seinem Ersuchen statt, was die (angeblichen) Mandanten, welche sich der Entbindung vom Anwaltsgeheimnis widersetzt hatten - die Y._ AG und X._ -, erfolglos beim Verwaltungsgericht des Kantons Zürich anfochten (Entscheid vom 31. Mai 2007).
B. Am 9. September 2007 haben X._ und die Y._ AG gemeinsam beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten eingereicht mit dem Antrag, sowohl den Entscheid des Verwaltungsgerichts als auch den Beschluss der Aufsichtskommission aufzuheben.
Rechtsanwalt E._ schliesst auf Abweisung der Beschwerde, während das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Aufsichtskommission über die Anwältinnen und Anwälte im Kanton Zürich sowie das Bundesamt für Justiz haben je auf Stellungnahme verzichtet.

Erwägungen:
1. 1.1 Das Bundesgesetz vom 23. Juni 2000 über die Freizügigkeit der Anwältinnen und Anwälte (Anwaltsgesetz, BGFA; SR 935.61) regelt die Berufspflichten abschliessend. Es bildet Teil des Bundesverwaltungsrechts, weshalb der - kantonal letztinstanzliche - Verwaltungsgerichtsentscheid betreffend die Entbindung des Beschwerdegegners vom Anwaltsgeheimnis (vgl. <ref-law>) mit Beschwerde in öffentlich-rechtlichen Angelegenheiten angefochten werden kann (Art. 82 lit. a in Verbindung mit Art. 86 Abs. 1 lit. d und Art. 90 BGG). Weil keiner der Ausschlussgründe von <ref-law> erfüllt ist und den Beschwerdeführern nach <ref-law> die Rechtsmittellegitimation zukommt, ist insoweit auf die Beschwerde einzutreten.
1.2 Unzulässig ist die Beschwerde jedoch, soweit sie sich auch gegen den erstinstanzlichen Beschluss der Aufsichtskommission über die Anwältinnen und Anwälte im Kanton Zürich richtet. Wie schon mit der Verwaltungsgerichtsbeschwerde unter der Herrschaft des bis Ende 2006 in Kraft stehenden Bundesgesetzes über die Organisation der Bundesrechtspflege (vgl. Art. 98 lit. g OG) kann auch mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten nur der Entscheid der letzten kantonalen Instanz angefochten werden.
2. 2.1 Die Rechtsanwälte unterstehen zeitlich unbegrenzt und gegenüber jedermann dem Berufsgeheimnis über alles, was ihnen infolge ihres Berufs von ihrer Klientschaft anvertraut worden ist (<ref-law>; vgl. auch <ref-law>). Zu den Tatsachen, welche unter den Schutz des Anwaltsgeheimnisses fallen, gehört schon der Umstand des Bestehens eines Mandats zwischen dem Rechtsanwalt und seinem Klienten. Deshalb setzt die klageweise Einforderung einer Honorarforderung praxisgemäss eine vorgängige Befreiung des Anwalts von seiner Schweigepflicht voraus (vgl. Urteile 1S.5/2006 vom 5. Mai 2006, in: SJ 2006 I S. 489, E. 5.3.1; 2P.313/1999 vom 8. März 2000, E. 2; Näheres bei Michael Pfeifer, in: Fellmann/Zindel [Hrsg.], Kommentar zum Anwaltsgesetz, Zürich/Basel/Genf 2005, N 65 ff. zu Art. 13). Verweigert der Mandant die Entbindung vom Anwaltsgeheimnis, so kann sich der Rechtsanwalt, der sein Honorar auf dem Rechtsweg einzutreiben sucht, mit einem Gesuch an die Aufsichtsbehörde wenden.
2.2 Vorliegend ist der Beschwerdegegner unbestrittenermassen erfolglos an die Beschwerdeführer gelangt, bevor er der Aufsichtskommission über die Anwältinnen und Anwälte im Kanton Zürich die Entbindung vom Anwaltsgeheimnis beantragt hat. Weil er seinen Geschäftssitz in Zürich hat, war die dortige Aufsichtsbehörde ohne weiteres zuständig (Art. 5 Abs. 1 in Verbindung mit Art. 13 und Art. 14 BGFA; vgl. auch § 33 ff. des Zürcher Anwaltsgesetzes). Mit Blick auf die Tatsache, das ein solcher behördlicher Entbindungsentscheid ein Rechtsschutzinteresse voraussetzt, hat die Aufsichtskommission alsdann geprüft, ob das Bestehen einer Honorarforderung bzw. eines Mandatsverhältnisses glaubhaft sei. Diese Frage hat sie aufgrund der vom Beschwerdeführer eingereichten Dokumente (Rechnung, Mahnungsschreiben und weiterer Korrespondenz) bejaht und mit Beschluss vom 1. Februar 2007 die verlangte Entbindung gewährt.
2.3 Entgegen den Vorbringen in der Beschwerdeschrift ist dieser Beschluss bzw. der ihn schützende Verwaltungsgerichtsentscheid nicht zu beanstanden: Die Beschwerdeführer verkennen offensichtlich Bedeutung und Tragweite des Entbindungsentscheids. Ein solcher hat keinerlei materielle Rechtswirkungen, sondern ermöglicht es dem gesuchstellenden Anwalt bloss, ohne Verletzung des disziplinar- und strafrechtlich geschützten Berufsgeheimnisses die behauptete Honorarforderung auf dem Klageweg geltend zu machen. Auch wenn die Aufsichtsbehörde in der Begründung ihres Beschlusses festhält, sie erachte das Bestehen eines Mandatsverhältnisses als "glaubhaft", präjudiziert dies einen späteren Zivilprozess über die Honorarforderung in keiner Weise. Die einzige unmittelbare Rechtswirkung, welche der Entbindungsentscheid für den betroffenen Mandanten hat, liegt darin, dass dieser in jenem Umfang, in dem es für die Geltendmachung der Honorarforderung notwendig ist, des ihm ansonsten zustehenden Schutzes durch das Anwaltsgeheimnis verlustig geht. Nachdem die Beschwerdeführer das Bestehen eines Mandatsverhältnisses überhaupt bestreiten, ist nicht einzusehen, wieso sie sich der Entbindung des Beschwerdegegners vom Anwaltsgeheimnis widersetzt und den dahingehenden Beschluss der Aufsichtskommission angefochten haben. Es hätte ihren Interessen wohl besser entsprochen, den Beschwerdegegner - selbstverständlich ohne Anerkennung irgendeiner Rechtspflicht - selber vom (ihres Erachtens nicht bestehenden und darum auch keines Schutzes bedürfenden) Anwaltsgeheimnis zu entbinden und ihre Gegenargumente alsdann im materiellrechtlichen Zivilprozess einzubringen. Dies umso mehr, als der Einwand, es bestehe entgegen den Behauptungen des Rechtsanwalts gar kein Mandatsverhältnis, im Verfahren auf Entbindung vom Anwaltsgeheimnis regelmässig untauglich ist. Sobald Anhaltspunkte dafür bestehen, dass die gegenteilige Behauptung des Anwalts zutreffend sein könnte, hat die Aufsichtsbehörde die Entbindung zu gewähren. Zu verweigern ist eine verlangte Entbindung nur dann, wenn die Klientschaft ihrerseits ein höherrangiges Interesse an der Geheimhaltung des Mandatsverhältnisses hat.
2.4 Nach dem Gesagten kann insoweit weder von einer Verletzung des Willkürverbots (<ref-law>) noch des Fairnessgebots (<ref-law>) die Rede sein. Soweit sich die Beschwerdeführer im vorliegenden Zusammenhang ausserdem auf <ref-law> berufen, genügen ihre Vorbringen den gesetzlichen Begründungsanforderungen von <ref-law> offensichtlich nicht, weshalb nicht weiter auf sie einzugehen ist. Nicht rechtsgenüglich dargetan ist ferner auch, weshalb der Anspruch auf rechtliches Gehör (<ref-law>; vgl. <ref-ruling> E. 3.2 S. 236; <ref-ruling> E. 2.2 S. 504 f.) verletzt worden sein sollte.
3. Schliesslich verstösst der Umstand, dass die Beschwerdeführer im kantonalen Verfahren zur Bezahlung der Gerichtskosten verpflichtet wurden, nicht gegen das Willkürverbot (<ref-law>; vgl. <ref-ruling> E. 5a S. 70). Sie haben sich vor der Aufsichtskommission der Befreiung des Beschwerdeführers vom Anwaltsgeheimnis förmlich widersetzt und sich so im Verfahren als Gegenpartei konstituiert. Daran ändert nichts, dass sie in ihrer Eingabe sowohl die Zuständigkeit der Aufsichtskommission als auch das Bestehen eines Mandatsverhältnisses bestritten haben. Mit Blick auf diesen Rechtsstandpunkt hätten die Beschwerdeführer ohne weiteres auf Opposition verzichten und sich stattdessen mit dem blossen Hinweis begnügen können, mangels eines Mandatsverhältnisses würden sie durch die anbegehrte Entbindung vom Berufsgeheimnis gar nicht berührt. Auch im kantonalen Beschwerdeverfahren verfügten sie offensichtlich über Parteistellung, zumal sie selber den Beschluss der Aufsichtskommission beim Verwaltungsgericht angefochten haben. Nachdem sie in beiden kantonalen Verfahren unterlegen sind, konnten sie ohne Willkür mit Kosten belastet werden.
4. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten erweist sich demnach als unbegründet, soweit auf sie einzutreten ist.
Bei diesem Verfahrensausgang werden die Beschwerdeführer kostenpflichtig (vgl. Art. 65 f. BGG). Parteientschädigung ist keine auszurichten, da der Beschwerdegegner als Anwalt in eigener Sache gehandelt hat und das vorliegende Verfahren für ihn mit keinem besonderen Aufwand verbunden war (vgl. <ref-law>; vgl. zur analogen Regelung unter der Herrschaft des bis Ende 2006 in Kraft stehenden Bundesgesetzes über die Organisation der Bundesrechtspflege: <ref-ruling> E. 3 S. 415; <ref-ruling> E. 4.1 S. 116).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'500.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, der Aufsichtskommission über die Anwältinnen und Anwälte im Kanton Zürich sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
Lausanne, 27. Mai 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Häberli