Sachverhalt:
A. Die Schweizerische Eidgenossenschaft, der Kanton Tessin und die Gemeinde Muralto erliessen durch das Ufficio esazione e condoni des Kantons am 21. Januar 2004 gegenüber X._, Monaco, gestützt auf Sicherstellungsverfügungen drei Arrestbefehle (Nrn. 1, 2, 3) für Steuerforderungen im Umfang von insgesamt über 33 Mio. Franken. In den Arrestbefehlen wurden die Arrestgegenstände wie folgt bezeichnet:
"Bei der Bank Z._, 7500 St. Moritz, alle Guthaben des Arrestschuldners; insbesondere Kontoguthaben, Wertschriften, Edelmetalle, Treuhanddepots, Safe-Inhalte, die auf den Namen des Schuldners oder auf den Namen von Frau Y._, gestorben am 20.03.2003, lauten; wie auch jeden Wert, keinen ausgeschlossen, welcher entweder auf den Namen des Schuldners oder auf den Namen von Frau Y._ eingetragen und/oder in dessen Eigentum ist oder bei dem der Schuldner oder Frau Y._ als Wirtschaftsberechtigter sich erweist. Insbesondere das Konto A._, das Konto n. 4 und das Konto n. 5. Alles soweit verarrestierbar, bis zur Deckung der Arrestforderung nebst Zinsen und Kosten."
Das Betreibungsamt Oberengadin vollzog die Arreste am 22. Januar 2004 gemäss Arrestbefehlen und nannte als Arrestgegenstände - in wörtlicher Wiederholung der Angaben in den Arrestbefehlen - auch jeden Vermögenswert bei der Bank Z._ in St. Moritz, bei dem sich "der Schuldner oder Frau Y._ als [wirtschaftlich berechtigt] erweist". Hiergegen erhob die Bank Z._ Beschwerde mit dem Begehren, die Arreste seien insoweit aufzuheben, als die Arrestlegung auf allfällige Vermögenswerte und Guthaben angeordnet worden sei, bei denen X._ und/oder Y._ als wirtschaftlich Berechtigte erscheinen.
B. Der Kantonsgerichtsausschuss von Graubünden als Aufsichtsbehörde über Schuldbetreibung und Konkurs hiess die Beschwerde mit Entscheid vom 16. März 2004 gut und hob den Arrestvollzug des Betreibungsamtes insoweit auf, als er sich auf Vermögenswerte bei der Bank Z._ in St. Moritz bezieht, welche nicht auf den Namen von X._ oder Y._ lauten, sondern diese lediglich daran wirtschaftlich Berechtigte sein sollen.
C. Die Schweizerische Eidgenossenschaft, der Kanton Tessin und die Gemeinde Muralto haben den Entscheid der kantonalen Aufsichtsbehörde mit Beschwerdeschrift vom 1. April 2004 (rechtzeitig) an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts weitergezogen und beantragen die Aufhebung des angefochtenen Entscheides und die Bestätigung des Arrestvollzuges des Betreibungsamtes.
Die Aufsichtsbehörde schliesst ohne Gegenbemerkungen (Art. 80 OG) auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Bank Z._ als Beschwerdegegnerin beantragt ebenfalls die Abweisung. Weitere Vernehmlassungen sind nicht eingeholt worden.

Die Kammer zieht in Erwägung:
1. 1.1 Die Aufsichtsbehörde hat den Arrestvollzug des Betreibungsamtes nur insoweit aufgehoben, als er sich auf Vermögenswerte bei der Beschwerdegegnerin in St. Moritz bezieht, welche nicht auf den Namen von X._ oder Y._ lauten, diese aber daran wirtschaftlich Berechtigte sein sollen. Daraus folgt, dass der Arrestvollzug im Übrigen wirksam ist, was von der Beschwerdegegnerin übrigens weder vor der kantonalen Behörde in Frage gestellt wurde noch im vorliegenden Verfahren bestritten wird. Somit ergibt sich, dass die Aufsichtsbehörde den Arrestvollzug in positiver - im Vergleich zum angefochtenen Entscheid deutlicherer - Formulierung in folgendem Umfang als zulässig erachtet hat (die von der Aufsichtsbehörde aufgehobene Formulierung ist durchgestrichen):
"Bei der Bank Z._, 7500 St. Moritz, alle Guthaben des Arrestschuldners; insbesondere Kontoguthaben, Wertschriften, Edelmetalle, Treuhanddepots, Safe-Inhalte, die auf den Namen des Schuldners oder auf den Namen von Frau Y._, gestorben am 20.03.2003, lauten; wie auch jeden Wert, keinen ausgeschlossen, welcher entweder auf den Namen des Schuldners oder auf den Namen von Frau Y._ eingetragen und/oder in dessen Eigentum ist oder bei dem der Schuldner oder Y._ als Wirtschaftsberechtigter sich erweist. Insbesondere das Konto A._, das Konto n. 4 und das Konto n. 5. Alles soweit verarrestierbar, bis zur Deckung der Arrestforderung nebst Zinsen und Kosten."
1.2 Die Aufsichtsbehörde hat den Arrest in Bezug auf die Konten A._, Nr. 4 und Nr. 5 nicht aufgehoben. Soweit die Beschwerdeführer rügen, der Arrestvollzug sei insbesondere in Bezug auf die Konten A._, Nr. 4 und Nr. 5 zu Unrecht als unzulässiger Sucharrest aufgehoben worden, kann auf ihre Beschwerde nicht eingetreten werden. Die Beschwerdeführer machen insoweit weder ein schützenswertes Interesse an der Aufhebung oder Abänderung (vgl. Art. 21 SchKG) des angefochtenen Entscheides geltend, noch ist ein solches Interesse ersichtlich (<ref-ruling> E. 3 S. 44; <ref-ruling> E. 1 S. 3). Die Beschwerde ist zulässig, soweit die Beschwerdeführer meinen, der Arrest sei über die genannten Konten auszuweiten, und es sich dabei nicht um ein neues und unzulässiges Vorbringen handelt.
2. 2.1 Die Aufsichtsbehörde hat erwogen, dass die Formulierung in den Arrestbefehlen, wonach alle Werte des Schuldners bei der Beschwerdegegnerin in St. Moritz zu verarrestieren seien, bei denen sich erweise, dass X._ oder Y._ daran wirtschaftlich berechtigt seien, die Arrestgegenstände ungenügend spezifiziere und faktisch auf einen verpönten Sucharrest hinauslaufe. Weiter werde nirgends glaubhaft gemacht, dass die genannten Personen an Vermögenswerten, welche bei der Beschwerdegegnerin in St. Moritz lägen und auf den Namen Dritter lauteten, wirtschaftlich berechtigt seien. Der Arrestbefehl sei insoweit nichtig.
2.2 Strittig ist, ob die Aufsichtsbehörde den Arrestvollzug in Bezug auf die in den Arrestbefehlen verwendete Formulierung "[jeder Wert] ... bei dem [sich] der Schuldner oder Frau Y._ als [wirtschaftlich berechtigt] erweist" aufheben durfte.
2.2.1 Die Aufsichtsbehörde bezieht sich mit ihrer Erwägung, dass die strittige Formulierung in den Arrestbefehlen die Arrestgegenstände ungenügend spezifiziere, auf den im Beschwerdeverfahren gerügten Umstand, dass im Arrestbefehl der Name derjenigen Person(en), die Vermögenswerte des Arrestschuldners ohne eigene wirtschaftliche Berechtigung hält (halten), nicht bezeichnet wird. Die Rechtsprechung leitet aus dem mit der SchKG-Revision eingeführten Art. 272 Abs. 1 Ziff. 3 SchKG ab, dass zumindest die Namen derjenigen Dritten anzugeben sind, die lediglich formell Vermögenswerte, insbesondere Forderungen des Schuldners halten, damit der Arrest überhaupt durchführbar ist (<ref-ruling> E. 4a S. 97 mit Hinweis auf <ref-ruling> E. 6 S. 125; vgl. Gilliéron, Commentaire de la loi fédérale sur la poursuite pour dettes et la faillite, N. 36 a.E. zu Art. 274 SchKG). Im konkreten Fall fehlt in den Steuerarrestbefehlen - abgesehen von der Person Y._ - zumindest die Namensangabe von Dritten, denen Vermögen des Arrestschuldners lediglich formell gehören soll. Unter diesen Umständen ist nicht zu beanstanden, wenn die Aufsichtsbehörde zum Ergebnis gelangt ist, die Arrestbefehle seien insoweit nicht durchführbar und deren Vollzug aufzuheben (<ref-ruling> E. 2.3 S. 207), soweit Vermögenswerte, an denen X._ und/oder Y._ wirtschaftlich berechtigt seien, bei der Beschwerdegegnerin in St. Moritz zu verarrestieren seien.
2.2.2 An diesem Ergebnis vermag der Hinweis der Beschwerdeführer auf das Urteil des Bundesgerichts vom 17. Februar 1999 (BlSchK 2000 S. 142) nichts zu ändern. Gegenstand des zitierten Urteils war ein anhand einzelner Bankkonten konkretisierter und zulässiger Gattungsarrest (vgl. dazu Stoffel, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, N. 29 zu Art. 272 SchKG; Amonn/Walther, Grundriss des Schuldbetreibungs- und Konkursrechts, 7. Aufl. 2003, § 51 Rz. 35 und 50), genauso wie er - abgesehen von der fraglichen Formulierung - unbestrittenermassen vorliegt. Wie hier waren nicht alle Bankkonti bekannt. Anders als hier sollten dort ausschliesslich Guthaben eines bestimmten Bankkunden verarrestiert werden. Deshalb lässt sich jenem Urteil nichts entnehmen, was das Erfordernis nach <ref-ruling> E. 4a S. 97 in Frage stellt, wonach zumindest die Namen der Dritten anzugeben sind, die lediglich formell Vermögenswerte des Arrestschuldners halten, um den Arrest überhaupt durchzuführen.
2.2.3 Die Beschwerdeführer versuchen ebenso vergeblich, aus <ref-ruling> etwas für sich abzuleiten. Wohl wird in diesem - ein Pfändungsverfahren betreffenden - Entscheid festgehalten, dass die Betreibungsbehörden gestützt auf Art. 91 Abs. 4 SchKG von einer Bank die Angabe der Vermögenswerte verlangen können, an welchen der Betriebene wirtschaftlich berechtigt ist (<ref-ruling> E. 3.2 E. 241). Die für die Pfändung statuierte Auskunftspflicht gilt sinngemäss auch für den Arrestvollzug (Art. 275 SchKG; vgl. <ref-ruling> E. 2b S. 393). Das bedeutet, dass die Beschwerdegegnerin über die im Arrestbefehl genannten Arrestgegenstände Auskunft geben muss, also auch über Gegenstände und Guthaben, an denen nominell ein Dritter, und nicht der Schuldner berechtigt erscheint (vgl. Gilliéron, a.a.O., N. 50 f. und 57 zu Art. 275 SchKG); umgekehrt darf der Betreibungsbeamte nicht Nachforschungen über nicht im Arrestbefehl genannte Vermögenswerte anstellen oder verlangen (Reiser, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, N. 75 zu Art. 275 SchKG; Markus Müller-Chen, Die Auskunftspflicht Dritter beim Pfändungs- und Arrestvollzug, BlSchK 2000 S. 226). Im konkreten Fall kann demnach das Betreibungsamt ohne weiteres insbesondere über die in den Arrestbefehlen ausdrücklich aufgeführten Konten - unabhängig davon, wer daran formell berechtigt ist - Auskunft verlangen. Wenn aber in den Arrestbefehlen die Namensangabe von Dritten, denen - nicht genannte - Vermögenswerte des Arrestschuldners lediglich formell gehören, fehlt, und die Arrestbefehle insoweit nicht durchführbar sind (E. 2.2.1), darf der Betreibungsbeamte zum Arrestvollzug nicht selber Nachforschungen über entsprechende Dritte machen oder von der Beschwerdegegnerin weitere Auskünfte verlangen. Auch vor diesem Hintergrund ist das Ergebnis der Aufsichtsbehörde nicht zu beanstanden.
2.2.4 Die Aufsichtsbehörde hat - im Sinne einer Eventualerwägung - schliesslich festgehalten, es werde auch nirgends glaubhaft gemacht, dass X._ oder Y._ an (weiteren) Vermögenswerten, welche bei der Beschwerdegegnerin in St. Moritz lägen und auf den Namen Dritter lauteten, wirtschaftlich berechtigt seien. Die Beschwerdeführer kritisieren die Auffassung der Vorinstanz mit Hinweis auf deren Überprüfungsbefugnis. Darüber zu entscheiden, ob dem Gläubiger die Glaubhaftmachung gelungen sei, dass gewisse Vermögenswerte entgegen dem formellen Anschein dem Arrestschuldner zustehen, ist in der Tat Sache des Arrestrichters (<ref-ruling> E. 4a a.E. S. 97), bzw. - falls nicht wie in Steuergesetzen ausgeschlossen - des Einspracherichters (<ref-ruling> E. 2.2 und 2.3 S. 206). Demnach hätte die Aufsichtsbehörde über entsprechende Vorbringen gar nicht entscheiden können, vielmehr bleibt in der alleinigen Befugnis der Beschwerdeführer als Arrestbehörde (Art. 170 DBG; Art. 78 StHG; Art. 249 LT/TI), selber im Arrestbefehl die Arrestgegenstände oder zumindest den Namen von Personen anzugeben, die lediglich formell Vermögenswerte, insbesondere Forderungen des Schuldners halten. Soweit die Beschwerdeführer diesem Erfordernis nicht nachgekommen sind, ist der Arrest nicht durchführbar, und die Vorbringen der Beschwerdeführer sind unbehelflich.
2.3 Nach dem Dargelegten ergibt sich, dass der angefochtene Entscheid der Aufsichtsbehörde, mit welchem der Vollzug der Arrestbefehle insoweit aufgehoben worden ist, als er sich auf Vermögenswerte bei der Beschwerdegegnerin in St. Moritz bezieht, welche nicht auf den Namen von X._ oder Y._ lauten, sondern diese lediglich daran wirtschaftlich Berechtigte sein sollen, insgesamt vor Bundesrecht standhält.
3. Das Beschwerdeverfahren ist grundsätzlich kostenlos (Art. 20a Abs. 1 SchKG), und es darf keine Parteientschädigung zugesprochen werden (Art. 62 Abs. 2 GebV SchKG).

Demnach erkennt die Kammer:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Dieses Urteil wird den Beschwerdeführern, den Beschwerdegegnern (Bank Z._, vertreten durch Rechtsanwalt Georg Zondler; X._, Monaco, vertreten durch Avvocato Michele Franscini), dem Betreibungsamt Oberengadin und dem Kantonsgerichtsausschuss von Graubünden als Aufsichtsbehörde über Schuldbetreibung und Konkurs schriftlich mitgeteilt.
Lausanne, 19. Juli 2004
Im Namen der Schuldbetreibungs- und Konkurskammer
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber: