Sachverhalt: A. Die 1977 geborene K._ war seit 12. August 1999 als Büroangestellte in der Firma P._ AG tätig gewesen. Mit Schreiben vom 20. Mai 2001 löste die Arbeitgeberin das Arbeitsverhältnis unter Hinweis auf "difficultés économiques et financières" mit sofortiger Wirkung auf. Zunächst forderte K._ die Firma P._ AG mehrmals schriftlich zur Zahlung ausstehender Löhne auf. Schliesslich erhob sie Klage gegen die ehemalige Arbeitgeberin auf Bezahlung von Fr. 16'932.60, welche vom Gewerblichen Schiedsgericht Basel-Stadt mit Entscheid vom 6. Mai 2002 gutgeheissen wurde, und leitete für die offene Forderung Betreibung ein. Nachdem gegen den Zahlungsbefehl vom 28. Juni 2002 Rechtsvorschlag erhoben worden war, bewilligte das Zivilgericht Basel-Stadt mit Entscheid vom 19. August 2002 die definitive Rechtsöffnung. Mittlerweile waren das Domizil der Gesellschaft und der Eintrag über das letzte Mitglied des Verwaltungsrates im Handelsregister gelöscht worden. Der Aufforderung im Schweizerischen Handelsamtsblatt (SHAB) vom ......, innert 30 Tagen seit Erscheinen der Publikation dem zuständigen Handelsregisteramt ein allfälliges begründetes Interesse an der Aufrechterhaltung der Eintragung der Firma P._ AG - welche angeblich über keine verwertbaren Aktiven mehr verfüge - im Handelsregister schriftlich mitzuteilen, kam K._ mit Schreiben vom 5. September 2002 an das Handelsregisteramt des Kantons Basel-Stadt fristgemäss nach. Zu einer Löschung der Firma im Handelsregister kam es in der Folge nicht. Am 1. Oktober 2002 stellte K._ Antrag auf Insolvenzentschädigung bezüglich Lohnforderungen für die Zeit vom 1. April bis 20. Juli 2001 im Betrag von Fr. 13'125.-. Mit Verfügung vom 21. Oktober 2002 lehnte die Öffentliche Arbeitslosenkasse Basel-Stadt die Ausrichtung von Insolvenzentschädigung ab und gab zur Begründung an, über die Firma P._ AG sei noch kein Konkurs eröffnet worden und es liege auch keine offensichtliche Überschuldung der ehemaligen Arbeitgeberin vor, womit die Anspruchsvoraussetzungen nicht erfüllt seien. B. Dagegen liess K._ Beschwerde erheben mit dem Antrag, in Aufhebung der Verfügung vom 21. Oktober 2002 sei ihr eine Insolvenzentschädigung von Fr. 16'932.60 zuzüglich Zins zu 5 % seit 1. Mai 2001 zuzusprechen. Das Sozialversicherungsgericht Basel-Stadt hiess die Beschwerde mit Entscheid vom 17. März 2004 gut. C. Vertreten durch das Amt für Wirtschaft und Arbeit des Kantons Basel-Stadt, Kantonale Amtsstelle für Arbeitslosenversicherung, führt die Öffentliche Arbeitslosenkasse Basel-Stadt Verwaltungsgerichtsbeschwerde mit dem Rechtsbegehren, der kantonale Gerichtsentscheid vom 17. März 2004 sei aufzuheben, eventuell sei der Entscheid bezüglich der Höhe der Insolvenzentschädigung zu korrigieren, weil die Freistellungszeit nicht zum "Leistungsumfang der Insolvenzentschädigung" gehöre und die Verzinsungspflicht erst mit dem Datum der Anmeldung beginne. K._ lässt auf Abweisung der Verwaltungsgerichtsbeschwerde schliessen; eventualiter sei ihr in teilweiser Gutheissung der Verwaltungsgerichtsbeschwerde eine Insolvenzentschädigung von Fr. 9625.- zuzusprechen; subeventualiter sei die Sache mit der Anweisung, es sei abzuklären, wie sich der Betrag von Fr. 16'932.60 zusammensetze, und zur Neubeurteilung an das kantonale Gericht zurückzuweisen. Das Staatssekretariat für Wirtschaft (seco) beantragt, der Entscheid des kantonalen Gerichts vom 17. März 2004 sei aufzuheben.