Sachverhalt:
A. Am 3. Februar 2011 erliess die Staatsanwaltschaft Basel-Stadt, Abteilung Wirtschaftsdelikte, eine Nichtanhandnahmeverfügung. Dagegen erhob die X._ AG Beschwerde, welche das Appellationsgericht des Kantons Basel-Stadt, a.o. Präsident, mit Urteil vom 13. April 2011 guthiess, indem es die Nichtanhandnahmeverfügung aufhob und die Staatsanwaltschaft anwies, unverzüglich Ermittlungen gegen die unbekannte Täterschaft wegen Betrugs aufzunehmen.
B. Gegen den Beschwerdeentscheid des Appellationsgerichtes vom 13. April 2011 gelangte die Staatsanwaltschaft mit Beschwerde vom 25. Mai 2011 an das Bundesgericht. Sie beantragt, der angefochtene Beschwerdeentscheid sei aufzuheben und ihre erstinstanzliche Verfügung zu bestätigen.
Die X._ AG und das Appellationsgericht beantragen je die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Der angefochtene Rückweisungsentscheid schliesst das Strafverfahren nicht ab. Es handelt sich um einen strafprozessualen Zwischenentscheid im Sinne von Art. 78 Abs. 1 und Art. 80 Abs. 1 i.V.m. <ref-law>.
1.2 Sofern die Sachurteilsvoraussetzungen nicht ohne Weiteres aus den Akten ersichtlich werden, obliegt es grundsätzlich der beschwerdeführenden Partei darzulegen, inwiefern sie erfüllt sind (vgl. <ref-ruling> E. 1.1 S. 251, 353 E. 1 S. 356).
1.3 Als oberste rechtsprechende Behörde des Bundes soll sich das Bundesgericht in der Regel nur einmal mit der gleichen Streitsache befassen müssen. Nach ständiger Praxis zu <ref-law> ist ein Vor- oder Zwischenentscheid daher nur ausnahmsweise anfechtbar, sofern ein konkreter rechtlicher Nachteil droht, der auch durch einen (für die rechtsuchende Partei günstigen) Endentscheid nachträglich nicht mehr behoben werden könnte (<ref-ruling> E. 1.2 S. 263 mit Hinweisen).
1.4 Die beschwerdeführende Staatsanwaltschaft äussert sich zur Frage der Sachurteilsvoraussetzung von <ref-law> nicht. Ein nicht wieder gutzumachender Rechtsnachteil im Sinne der dargelegten Praxis ist hier nicht ersichtlich. Insbesondere fiele eine blosse Verlängerung oder Verteuerung des Verfahrens nicht darunter (<ref-ruling> E. 4 S. 141 mit Hinweisen). Damit erweist sich die Beschwerde als nicht zulässig. Die Prüfung allfälliger weiterer Eintretenshindernisse erübrigt sich im vorliegenden Fall.
2. Auf die Beschwerde ist nicht einzutreten.
Gerichtskosten sind nicht zu erheben (<ref-law>). Hingegen ist der anwaltlich vertretenen privaten Beschwerdegegnerin eine angemessene Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Basel-Stadt, Kasse der Staatsanwaltschaft, hat der privaten Beschwerdegegnerin eine Parteientschädigung von Fr. 2'500.-- zu entrichten.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, a.o. Appellationsgerichtspräsident, schriftlich mitgeteilt.
Lausanne, 22. Juli 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Aemisegger
Der Gerichtsschreiber: Forster