Sachverhalt:
A. Die Staatsanwaltschaft III Zürich führt eine Strafuntersuchung gegen A._ und weitere Angeschuldigte u.a. wegen Veruntreuung eines Teils des Aktien- und Partizipationsscheins-Kapitals der B._ AG, Rapperswil-Jona.
Ausgelöst wurde das Verfahren durch eine Strafanzeige von X._ und Y._ wegen Betrugs. Darin wurde den Angeschuldigten vorgeworfen, sie hätten die Anzeigeerstatter veranlasst, Aktionäre der B._ AG zu werden, die Eigentümerin des "Goldenen Chiemsee-Kessels" sei, eines bedeutenden kulturellen und kunsthistorischen Fundobjekts mit einem Kommerzialisierungswert von über einer Milliarde Euro. Allerdings sei den Anzeigeerstattern lediglich eine wertlose Replik präsentiert worden. Sie seien dadurch zu Investitionen in Höhe von 1.1 Mio. Euro in die Vermarktung des Kulturobjekts verleitet worden, für welche sie nie einen Gegenwert erhalten hätten.
Beim "Goldenen Chiemsee-Kessel" handelt es sich um einen im Chiemsee (in Bayern, Deutschland) entdeckten, ca. 11 kg schweren Kessel aus Goldblech, der mit keltischen Motiven verziert ist. Herkunft und Alter des Kessels sind streitig.
B. Mit Verfügung vom 28. November 2006 wurde der Chiemsee-Kessel von der zuständigen Strafverfolgungsbehörde als Beweismittel und zur allfälligen Deckung von Verfahrenskosten, Schadensdeckung etc. beschlagnahmt.
Am 30. April 2008 wies die Staatsanwaltschaft III des Kantons Zürich (im Folgenden: Staatsanwaltschaft) den Antrag auf Herausgabe des Chiemsee-Kessels an die B._ AG ab.
Diese Verfügung zog sie am 23. Mai 2008 in Wiedererwägung und ordnete, aus Gründen der Verhältnismässigkeit, um die Vermarktung des Chiemsee-Kessels nicht zu gefährden, dessen Herausgabe an die B._ AG an, unter Vorbehalt einer anderslautenden zivilrechtlichen Verfügung. Als Ersatzmassnahmen wurde die Beschlagnahme des Erlöses aus dem allfälligen Verkauf des Chiemsee-Kessels angeordnet und der B._ AG und A._ diesbezüglich verschiedene Weisungen auferlegt.
Gegen diese Freigabeverfügung erhoben X._ und Y._ Rekurs an die Oberstaatsanwaltschaft des Kantons Zürich. Überdies machten Drittansprecher mit Rekurs bzw. Wiedererwägungsgesuch selbständige Besitzrechte an dem Objekt geltend. Die Oberstaatsanwaltschaft leitete die Rekursschriften dem Einzelrichter in Strafsachen des Bezirksgerichts Meilen weiter, der nach <ref-law>/ZH zuständig sei, sofern die Beschlagnahme bzw. die Freigabe einen nicht wiedergutzumachenden Nachteil bewirke.
Am 23. September 2008 erliess die Staatsanwaltschaft eine 2. Wiedererwägungsverfügung. Sie hob ihre Freigabeverfügung vom 23. Mai 2008 auf und beantragte dem Einzelrichteramt des Bezirks Zürich, es sei die Hinterlegung des sogenannten "Goldenen Chiemsee-Kessels" zu genehmigen und es seien die für die Herausgabe erforderlichen Verfügungen zu erlassen. Gleichzeitig verfügte die Staatsanwaltschaft, dass der Chiemsee-Kessel bis zum Entscheid über den Hinterlegungsantrag unter Beschlag bleibe.
Der Einzelrichter in Strafsachen des Bezirksgerichts Meilen schrieb daraufhin den bei ihm hängigen Rekurs von X._ und Y._ als gegenstandslos geworden ab.
Gegen die Verfügung vom 23. September 2008 rekurrierte der Angeschuldigte A._. Auf dessen Rekurs trat die Oberstaatsanwaltschaft am 16. Oktober 2008 nicht ein.
C. Am 25. Februar 2009 trat die Einzelrichterin am Bezirksgericht Zürich auf den Hinterlegungsantrag der Staatsanwaltschaft nicht ein. Sie führte aus, die Staatsanwaltschaft könne den Drittansprechern Frist zur Einreichung von Zivilklagen ansetzen und müsse nicht den "Umweg" über die Hinterlegungsrichterin nehmen.
Daraufhin setzte die Staatsanwaltschaft am 6. April 2009 den Drittansprechern eine Frist von 30 Tagen, um Ansprüche betreffend den Chiemsee-Kessel im Rahmen einer Zivilklage gegen die B._ AG geltend zu machen; falls innerhalb dieser Frist keine diese Ansprüche sichernde zivilprozessuale vorsorgliche Massnahme erwirkt werde, werde der Chiemsee-Kessel der B._ AG herausgegeben. Die Staatsanwaltschaft beschlagnahmte den Erlös aus einem allfälligen Verkauf des Chiemsee-Kessels und wies die B._ AG und A._ an, sie stets unverzüglich über Standortwechsel des Kessels sowie über wesentliche Entwicklungen des Verkaufsprozesses zu orientieren. Zudem sei ein schweizerisches Bankkonto zu bestimmen, welches die Staatsanwaltschaft sperren könne, und der allfällige Käufer sei anzuweisen, Zahlungen für den Kessel ausschliesslich auf dieses Konto zu leisten.
D. Gegen diese Verfügung rekurrierten X._ und Y._ am 15. April 2009 an die Oberstaatsanwaltschaft des Kantons Zürich.
Diese wies den Rekurs am 18. Juni 2009 ab, soweit sie darauf eintrat. Sie vertrat die Auffassung, die strafprozessuale Freigabe des Objekts sei bereits mit Verfügung vom 23. September 2008 erfolgt. Bei der angefochtenen Verfügung handle es sich deshalb um eine reine Vollzugsverfügung, weshalb auf die Rügen der Rekurrenten zum strafprozessualen Beschlag und den von der Staatsanwaltschaft vorgesehenen Ersatzmassnahmen nicht mehr eingetreten werden könne.
E. Gegen diesen Entscheid haben X._ und Y._ am 20. Juli 2009 Beschwerde in Strafsachen an das Bundesgericht erhoben. Sie beantragen, der Rekursentscheid der Oberstaatsanwaltschaft und die Verfügung der Staatsanwaltschaft vom 6. April 2009 seien aufzuheben. Eventualiter sei nur der Rekursentscheid aufzuheben und die Sache zur materiellen Behandlung an die Oberstaatsanwaltschaft zurückzuweisen. Überdies ersuchen sie um Gewährung der aufschiebenden Wirkung. Die Beschwerdeführer vertreten die Auffassung, der Chiemsee-Kessel sei erst mit Verfügung vom 6. April 2009 aus der strafprozessualen Beschlagnahme entlassen worden, weshalb die Oberstaatsanwaltschaft auf ihre materiellen Rügen hätte eintreten müssen.
F. Die Staatsanwaltschaft beantragt, der angefochtene Entscheid der Oberstaatsanwaltschaft sei zu bestätigen. Die Oberstaatsanwaltschaft hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Der angefochtene Entscheid der Oberstaatsanwaltschaft bestätigt eine Verfügung der Staatsanwaltschaft über die Rückerstattung eines im Strafprozess beschlagnahmten Gegenstands. Es handelt sich dabei um eine strafrechtliche Angelegenheit i.S.v. <ref-law>. Der angefochtene Entscheid ist kantonal letztinstanzlich (<ref-law>/ZH; <ref-law>).
1.1 Es kann offen bleiben, ob der angefochtene Entscheid einen Endentscheid nach <ref-law> oder einen Zwischenentscheid nach <ref-law> darstellt. Er wäre auch anfechtbar, wenn man annehmen wollte, es handle sich um einen Zwischenentscheid. Die Beschwerdeführer verlangen die Aufrechterhaltung der Beschlagnahme, weil sie der Auffassung sind, der Chiemsee-Kessel könne im gegen A._ geführten Strafverfahren nach <ref-law> eingezogen und sodann nach <ref-law> zu ihren Gunsten verwendet werden. Sie befürchten, dass der Kessel im Falle einer Herausgabe an die B._ AG von A._, einzigem Verwaltungsrat der AG, dem Zugriff der Behörden entzogen und dessen Verwendung zugunsten der Beschwerdeführer vereitelt werden könnte. Bei dieser Sachlage könnte der angefochtene Entscheid für die Beschwerdeführer einen nicht wiedergutzumachenden Nachteil im Sinne von <ref-law> bewirken (Urteil 1B_212/2007 vom 12. März 2008 E. 1.3; ebenso <ref-ruling> E. 1b S. 100 f. zu Art. 87 Abs. 2 OG).
1.2 Gemäss <ref-law> ist zur Beschwerde in Strafsachen berechtigt, wer a) vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat; und b) ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat. Die anschliessende Liste (1.-6.) ist, wie sich aus dem Wort "insbesondere" ergibt, nicht abschliessend (<ref-ruling> E. 2.3 S. 230, mit Hinweis). Gemäss <ref-law> haben Geschädigte, soweit die darin genannten Voraussetzungen erfüllt sind, ein Recht auf Zusprechung eingezogener Vermögenswerte. Insofern haben sie ein rechtlich geschütztes Interesse an der Aufrechterhaltung einer strafprozessualen Beschlagnahme, die ihnen die Durchsetzung jenes Rechts ermöglichen soll (Urteil 1B_212/2007 vom 12. März 2008 E. 1.4 mit Hinweisen). Im Übrigen sind die Beschwerdeführer als Parteien des kantonalen Verfahrens unabhängig von ihrer Legitimation in der Sache befugt, die Verletzung formeller Verfahrensgarantien zu rügen (Urteil 1B_134/2008 vom 18. August 2008 E. 1.2 mit Hinweisen).
1.3 Nach dem Gesagten ist auf die Beschwerde in Strafsachen einzutreten.
2. Die Oberstaatsanwaltschaft ist auf die Rügen der Beschwerdeführer, wonach die Beschlagnahme des Chiemsee-Kessels im Hinblick auf die spätere Einziehung oder Verwertung aufrecht zu erhalten sei, nicht eingetreten, weil die strafprozessuale Freigabe gemäss § 98 Ziff. 1 und 2 StPO/ZH bereits erfolgt und seit dem Erlass des Hinterlegungsantrags und der entsprechenden, ausführlich begründeten Verfügung vom 23. September 2008 den Parteien kommuniziert sowie durch die Feststellungen des rechtskräftigen Rekursentscheids der Oberstaatsanwaltschaft vom 16. Oktober 2008 in Sachen A._ bestätigt worden sei. Aus diesen Entscheiden gehe hervor und sei durch den Entscheid des Bezirksgerichts Zürich vom 25. Februar 2009 betreffend Hinterlegung bestätigt worden, dass keine rechtlichen Gründe für einen weiteren strafprozessualen Beschlag mehr bestehen, mithin der Chiemsee-Kessel weder nach <ref-law>/ZH noch nach <ref-law>/ZH einer Verfügungsbeschränkung durch die Staatsanwaltschaft unterworfen sei, sondern dessen Herausgabe verfügt werden müsse. Unter den vorliegenden Umständen sei lediglich die Herausgabe an den Berechtigten blockiert, und es gelte nun zu entscheiden, wer näher am Recht stehe und welche Partei zur Wahrung ihrer Rechte den nächsten Schritt zu unternehmen habe. Bei der angefochtenen Verfügung handle es sich deshalb um eine reine Vollzugsverfügung, die es nicht mehr zulasse, den strafprozessualen Beschlag und die von der Staatsanwaltschaft vorgesehenen Ersatzmassnahmen erneut zur Diskussion zu stellen.
3. Die Beschwerdeführer werfen der Oberstaatsanwaltschaft vor, den Sachverhalt offensichtlich unrichtig festgestellt und ihren Anspruch auf rechtliches Gehör verletzt zu haben. Die Oberstaatsanwaltschaft messe der Verfügung der Staatsanwaltschaft vom 23. September 2008 eine Bedeutung zu, die ihr offensichtlich nicht zukomme. Die Staatsanwaltschaft habe zwar in ihren Erwägungen festgehalten, dass ihres Erachtens keine gesetzliche Grundlage mehr für die strafrechtliche Beschlagnahme bestehe, jedoch habe sie sich aufgrund der Unmöglichkeit, ohne zivilrechtlichen Sachentscheid die Verhältnisse vor der Beschlagnahme wiederherzustellen, gezwungen gesehen, den strafprozessualen Beschlag bis zur Genehmigung der Hinterlegung oder zur Einigung der Betroffenen aufrecht zu erhalten. Ein Hinterlegungsentscheid sei bis heute nicht ergangen, weshalb der Chiemsee-Kessel bis zur Verfügung vom 6. April 2009 unter strafprozessualem Beschlag gewesen sei.
Nichts anderes ergebe sich aus den übrigen, von der Oberstaatsanwaltschaft zitierten, Entscheiden. Insbesondere äussere sich der Entscheid der Hinterlegungsrichterin mit keinem Wort zur Frage, ob der Kessel noch unter strafprozessualer Beschlagnahme stehe oder nicht. Die Beschwerdeführer weisen zudem darauf hin, dass sie weder Partei des Rekursverfahrens i.S. A._ noch des Hinterlegungsverfahrens gewesen seien und ihnen diese Entscheide auch nicht zugestellt worden seien; vom Entscheid der Hinterlegungsrichterin hätten sie erst durch die Verfügung vom 6. April 2009 Kenntnis erhalten.
Der Rekurs der Beschwerdeführer gegen die ursprüngliche Freigabeverfügung vom 23. Mai 2008 sei vom Einzelrichter in Strafsachen infolge Gegenstandslosigkeit abgeschrieben worden, nachdem die Staatsanwaltschaft die Freigabeverfügung am 23. September 2008 durch Erlass einer neuen Verfügung aufgehoben habe. Eine gerichtliche Auseinandersetzung mit den Argumenten der Beschwerdeführer bzw. eine materielle Überprüfung der Beschlagnahmevoraussetzungen sei damit nicht erfolgt. Nun seien die Beschwerdeführer auch im zweiten Rekursverfahren nicht materiell gehört worden, sondern die Oberstaatsanwaltschaft habe ihnen, gestützt auf eine unhaltbare Begründung, erneut die Möglichkeit abgeschnitten, sich gegen die Freigabe des Chiemsee-Kessels zur Wehr zu setzen. Dies verletze <ref-law>.
4. Nach Auffassung der Oberstaatsanwaltschaft erfolgte die Aufhebung des strafprozessualen Beschlags bereits mit Verfügung vom 23. September 2008 und es wurde lediglich die Herausgabe an den Berechtigten aufgeschoben. Dies ist im Folgenden zu prüfen. Dabei kann die Auslegung einer auf kantonales Strafprozessrecht gestützten Verfügung vom Bundesgericht grundsätzlich nur unter dem Blickwinkel des Verfassungsrechts, namentlich des Willkürverbots, des Schutzes von Treu und Glauben (Art. 9 i.V.m. <ref-law>) und des rechtlichen Gehörs (<ref-law>), überprüft werden.
4.1 Disp.-Ziff. 1 der Verfügung vom 23. September 2008 lautet:
"Die Verfügung vom 23. Mai 2008 wird aufgehoben. Der Chiemsee-Kessel bleibt bis zum Entscheid über den vorstehenden Hinterlegungsantrag unter strafprozessualem Beschlag".
Weiter heisst es in der Rechtsmittelbelehrung:
"Wird geltend gemacht, die vorläufige Aufrechterhaltung der Beschlagnahme bewirke einen nicht wiedergutzumachenden Nachteil, ist der Rekurs an den Einzelrichter ... zu richten".
Das Dispositiv spricht daher klar für die Auffassung der Beschwerdeführer, wonach der strafprozessuale Beschlag nicht aufgehoben, sondern - zumindest vorläufig - aufrechterhalten worden sei.
4.2 Nichts anderes ergibt sich aus den Erwägungen der Verfügung: Zwar legte die Staatsanwaltschaft einleitend dar, weshalb ihrer Auffassung nach die Voraussetzungen für eine strafprozessuale Beschlagnahme nicht vorliegen. Jedoch sei die Verfügungsberechtigung und mithin das Besitzesrecht in Bezug auf den Kessel umstritten, und die Unternehmung C._, welche den Kessel vor der Beschlagnahme für die B._ AG verwahrt habe, wolle den Kessel nicht zurücknehmen. Zusammenfassend hielt die Staatsanwaltschaft deshalb Folgendes fest:
"Die angefochtene Freigabeverfügung vom 23. Mai 2008 ist aufzuheben. Damit gelangt der Kessel für die Übergangszeit bis zum Entscheid über den Hinterlegungsantrag erneut unter die Herrschaft der Verfügungen vom 28.11.2006, 22.12.2006 und 30.04.2008. Auch wenn nach Auffassung der Staatsanwaltschaft III keine gesetzliche Grundlage für die strafrechtliche Beschlagnahme mehr besteht, zwingt die Unmöglichkeit, ohne zivilrechtlichen Sachentscheid die Verhältnisse vor der Beschlagnahme wiederherzustellen, die Strafverfolgungsbehörden dazu, den strafprozessualen Beschlag bis zur Genehmigung der Hinterlegung oder zur Einigung der Parteien aufrecht zu erhalten."
4.3 Damit ergibt sich aus dem Dispositiv und den Erwägungen klar, dass der strafprozessuale Beschlag nicht aufgehoben, sondern vorläufig aufrechterhalten werden sollte. Nicht klar geregelt wurde dagegen, ob der strafprozessuale Beschlag durch eine neue, separat anfechtbare Freigabeverfügung der Staatsanwaltsschaft erfolgen sollte (so die Auffassung der Beschwerdeführer), oder automatisch mit der Genehmigung der Hinterlegung bzw. der Einigung der Parteien enden sollte.
Die Annahme einer auflösenden Bedingung erscheint insofern problematisch, als die Beschwerdeführer nicht Partei des Hinterlegungsverfahrens waren und ihnen der Hinterlegungsentscheid auch nicht zugestellt worden ist.
Wie es sich damit verhält, kann jedoch offen bleiben, da die (vermeintliche) Bedingung nie eingetreten ist: Weder haben sich die Parteien geeinigt, noch wurde der Hinterlegungsantrag genehmigt; vielmehr ist die Hinterlegungsrichterin auf den Hinterlegungsantrag nicht eingetreten. Unter diesen Umständen muss davon ausgegangen werden, dass der strafprozessuale Beschlag noch andauerte und erst mit Verfügung vom 6. April 2009 aufgehoben wurde.
4.4 Diese Auslegung drängt sich auch unter Beachtung des Anspruchs der Beschwerdeführer auf rechtliches Gehör auf (<ref-law>):
Im Zeitpunkt des Erlasses der (zweiten) Wiedererwägungsverfügung vom 23. September 2008 war ein Rekurs der Beschwerdeführer gegen die Freigabeverfügung vom 23. Mai 2008 vor dem Einzelrichter in Strafsachen am Bezirksgericht Meilen hängig. Dieser ging - wie die Beschwerdeführer - davon aus, dass der Rekurs mit Aufhebung der Freigabeverfügung gegenstandslos geworden sei, weil das Anfechtungsobjekt des Rekurses entfallen und den Rekursanträgen der Beschwerdeführer in der Wiedererwägungsverfügung der Staatsanwaltschaft entsprochen worden sei (vgl. Abschreibungsverfügung vom 9. Oktober 2008). Die Beschwerdeführer (wie auch der Einzelrichter) gingen somit - für die Staatsanwaltschaft erkennbar - davon aus, dass der Wiedererwägungsentscheid vom 23. September 2008 sie nicht beschwere und deshalb kein Anlass bestehe, dagegen zu rekurrieren.
Die von der Oberstaatsanwaltschaft vertretene Auslegung, wonach die strafprozessuale Freigabe bereits mit der Wiedererwägungsverfügung vom 23. September 2008 erfolgt sei, kam unter diesen Umständen für die Beschwerdeführer überraschend und hatte zur Folge, dass diesen der Rechtsweg abgeschnitten wurde.
4.5 Die von der Oberstaatsanwaltschaft erwähnten weiteren Entscheide ändern nichts an dieser Beurteilung: In ihrem Entscheid vom 16. Oktober 2008 trat die Oberstaatsanwaltschaft auf den Rekurs des Angeschuldigten A._ gegen die Verfügung vom 23. September 2008 nicht ein. Abgesehen davon, dass die Erwägungen dieses Entscheids unklar sind, wurde dieser Entscheid den Beschwerdeführern nicht zugestellt. Der zivilrechtliche Entscheid der Hinterlegungsrichterin ist für die Frage des strafprozessualen Beschlags ohne Bedeutung, wie die Beschwerdeführer zu Recht darlegen.
4.6 Unter diesen Umständen hätte die Oberstaatsanwaltschaft auf die materiellen Rügen der Beschwerdeführer gegen die Freigabe des Chiemsee-Kessels eintreten müssen, sofern sie sich als zuständig erachtete. Es ist nicht Aufgabe des Bundesgerichts, die streitigen strafprozessualen Fragen erstinstanzlich zu prüfen.
5. Die Beschwerde ist somit gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache zu neuer Beurteilung an die Oberstaatsanwaltschaft zurückzuweisen. Dieser steht es frei, die Sache an den Einzelrichter in Strafsachen weiterzuleiten, sofern sie zum Ergebnis kommt, dieser sei für die Beurteilung der Freigabe des Chiemsee-Kessels zuständig (wie beim ersten Rekurs der Beschwerdeführer gegen die Freigabeverfügung vom 23. Mai 2008 geschehen).
Mit der Gutheissung der Beschwerde wird der Antrag auf Gewährung der aufschiebenden Wirkung gegenstandslos.
Bei diesem Ausgang des Verfahrens obsiegen die Beschwerdeführer und haben Anspruch auf eine Parteientschädigung (<ref-law>). Dem Kanton sind keine Kosten aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Rekursentscheid der Oberstaatsanwaltschaft des Kantons Zürich vom 18. Juni 2009 wird aufgehoben. Die Sache wird zu neuer Beurteilung im Sinne der Erwägungen an die Oberstaatsanwaltschaft zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton Zürich hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Beschwerdeführern, der Staatsanwaltschaft III und der Oberstaatsanwaltschaft des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 8. September 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber