Sachverhalt:
A.
A._ (nachfolgend: Beschuldigter) reiste am 7. Januar 2019 von Deutschland kommend über den Grenzübergang Basel/Weil-Autobahn in die Schweiz ein. Dabei wurde er von der Grenzwache kontrolliert und von dieser wegen Einreise ohne gültiges Reisedokument und ohne Visum verzeigt. Nach der mündlichen Befragung wurde ihm ein Formular "Erklärung betreffend Zustellungsdomizil in der Schweiz" vorgelegt, gemäss dem er entweder eine Kontaktperson mit Wohnsitz in der Schweiz als Schweizer Zustelladresse angeben oder die Adresse einer für die Entgegennahme von Zustellungen zuständigen Mitarbeiterin der Strafbefehlsabteilung der Staatsanwaltschaft des Kantons Basel-Stadt als Zustellungsdomizil bezeichnen sollte. Der Beschuldigte liess auf dem von ihm unterzeichneten Formular die letztere Variante ankreuzen.
B.
Mit Strafbefehl vom 9. April 2019 verurteilte die Staatsanwaltschaft den Beschuldigten wegen rechtswidriger Einreise gemäss Ausländergesetz und sanktionierte ihn mit einer bedingten Geldstrafe von 10 Tagessätzen zu Fr. 30.--, bei einer Probezeit von zwei Jahren, sowie mit einer Busse von Fr. 100.--, bei schuldhafter Nichtbezahlung umwandelbar in eine Ersatz-Freiheitsstrafe von einem Tag. Zudem wurden ihm die Kosten des Strafbefehlsverfahrens in der Höhe von Fr. 358.60 auferlegt. Gleichentags nahm die für die Entgegennahme von Zustellungen zuständige Mitarbeiterin der Strafbefehlsabteilung der Staatsanwaltschaft den Strafbefehl entgegen und versandte eine Orientierungskopie davon mit eingeschriebener Post an die ausländische Wohnadresse des Beschuldigten in Brasilien.
C.
Mit E-Mail vom 30. Juli 2019 erhob der Beschuldigte Einwände gegen den Strafbefehl und dessen Zustellung. Mit Verfügung vom 4. September 2019 stellte die Präsidentin des Strafgerichts Basel-Stadt die Nichtigkeit des Strafbefehls vom 9. April 2019 fest und retournierte die Akten an die Staatsanwaltschaft zum Erlass eines neuen Strafbefehls und zur rechtshilfeweisen Zustellung desselben an den Beschuldigten.
D.
Gegen die Verfügung der Strafgerichtspräsidentin vom 4. September 2019 erhob die Staatsanwaltschaft StPO-Beschwerde mit dem Antrag, die Verfügung sei aufzuheben und es sei festzustellen, dass der Strafbefehl vom 9. April 2019 (nach gültiger fristauslösender Zustellung und Ablauf der Einsprachefrist) in Rechtskraft erwachsen sei. Das Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, wies die Beschwerde mit Entscheid vom 31. März 2020 ab.
E.
Gegen den Entscheid des Appellationsgerichtes gelangte die Staatsanwaltschaft mit Beschwerde vom 19. Mai 2020 an das Bundesgericht. Sie beantragt neben der Aufhebung des angefochtenen Entscheides die Feststellung, dass der Strafbefehl vom 9. April 2019 rechtskräftig geworden sei. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Appellationsgericht beantragt mit Stellungnahme vom 2. Juni 2020 die Abweisung der Beschwerde, während von der Strafgerichtspräsidentin innert angesetzter Frist keine Vernehmlassung einging. Der im Ausland domizilierte Beschuldigte wurde nicht in das Verfahren einbezogen. Er hat sich am vorinstanzlichen Beschwerdeverfahren nicht beteiligt. Wie sich aus den nachfolgenden Erwägungen ergibt, ist er durch das vorliegende Urteil auch nicht beschwert.

Erwägungen:
1.
1.1. Ist in einem Kanton eine übergeordnete staatsanwaltliche Behörde für die Strafverfolgung aller Straftaten im ganzen Kantonsgebiet zuständig, kann grundsätzlich nur diese Behörde (Oberstaatsanwaltschaft, Generalstaatsanwaltschaft usw.) oder ein Mitglied der obersten Geschäftsleitung einer kantonalen Staatsanwaltschaft mit Beschwerde in Strafsachen an das Bundesgericht gelangen (Art. 81 Abs. 1 lit. b Ziff. 3 BGG i.V.m. <ref-law>; <ref-ruling> E. 1.5.2 S. 200). Die Beschwerdeschrift ist unterzeichnet vom baselstädtischen Ersten Staatsanwalt und einem Leitenden Staatsanwalt; die Staatsanwaltschaft des Kantons Basel-Stadt ist zudem für Strafverfolgungen im ganzen Kanton grundsätzlich zuständig. Die Beschwerdelegitimation ist damit gegeben.
1.2. Die streitige Verfügung schliesst das Strafverfahren nicht definitiv ab. Die Staatsanwaltschaft wird vielmehr angewiesen, in der hängigen Strafsache einen neuen förmlichen Strafbefehl zu erlassen und diesen dem Beschuldigten auf dem Rechtshilfeweg (fristauslösend) zu eröffnen. Die Vorinstanz hat dieses Vorgehen bestätigt und die von der Staatsanwaltschaft dagegen erhobene Beschwerde (vollständig) abgewiesen. Damit liegt faktisch ein kantonal letztinstanzlicher Rückweisungsentscheid vor. Dieser ist in der vorliegenden Konstellation - unter dem Gesichtspunkt des nicht wieder gutzumachenden Rechtsnachteils, <ref-law> - grundsätzlich anfechtbar, zumal ein von der Staatsanwaltschaft als bundesrechtswidrig erachtetes Vorgehen im Rückweisungsbeschluss definitiv festgelegt wird und ihr kein inhaltlicher Entscheidungsspielraum mehr verbliebe (vgl. <ref-ruling> E. 4.2 S. 481 f., E. 5.2 S. 483-485; nicht amtl. publ. E. 1.2.2 von <ref-ruling>; je mit Hinweisen). Im Übrigen haben die kantonalen Gerichte die Staatsanwaltschaft dazu verpflichtet, ein ihrer Ansicht nach nichtiges Straferkenntnis neu auszufertigen und ihre Zustellungspraxis zu ändern, indem in analogen Fällen der beschwerliche Weg der internationalen Rechtshilfe in Strafsachen zu beschreiten wäre. Die aufgeworfenen Rechtsfragen erscheinen zudem von grundsätzlicher und erheblicher Bedeutung (vgl. nicht amtl. publ. E. 1.2.3 von <ref-ruling>).
2.
2.1. Die Vorinstanz erwägt im Wesentlichen Folgendes:
Streitig sei zwischen den kantonalen Strafbehörden, ob der Strafbefehl vom 9. April 2019, wie von der Staatsanwaltschaft vertreten, rechtskonform und fristauslösend eröffnet worden und mangels rechtzeitiger und formgerechter Einsprache in Rechtskraft erwachsen sei, oder ob der Strafbefehl ungültig eröffnet worden und damit nichtig sei. Straferkenntnisse seien grundsätzlich auf dem Wege der internationalen Rechtshilfe in Strafsachen zu eröffnen. Eine Ausnahme liege dann vor, wenn zwischen der Schweiz und dem betroffenen ausländischen Staat eine völkerrechtliche Regelung bestünde, die eine vereinfachte direkte Zustellung von Straferkenntnissen auf dem postalischen Wege zuliesse. Solches sei im internationalen Verkehr zwischen der Schweiz und Brasilien aber nicht staatsvertraglich vereinbart worden.
Die auf innerstaatliches Recht gestützte Fiktion einer Zustellung in der Schweiz an die Adresse der Staatsanwaltschaft erscheine in diesem Zusammenhang problematisch. Deren Ansicht, in Fällen wie dem vorliegenden werde bereits durch den blossen Erlass des Strafbefehls die zehntägige gesetzliche Einsprachefrist ausgelöst, führe de facto dazu, dass beschuldigte Personen in vielen Fällen ihres Einspracherechtes verlustig gingen, bevor sie überhaupt davon hätten Kenntnis nehmen können. Bis zum Erhalt der per Einschreiben versendeten "Orientierungskopie" habe die beschuldigte Person in der Regel nicht einmal Kenntnis davon, dass ein Strafbefehl gegen sie erging. Wie sich gerade im vorliegenden Fall gezeigt habe, könne die Versendung einer eingeschriebenen Postsendung ins Ausland ohne Weiteres eine Woche oder mehr in Anspruch nehmen. Auch sei zu beachten, dass die Übergabe einer Sendung an eine ausländische Poststelle gemäss StPO keine fristwahrende Wirkung habe. Dem Beschuldigten sei es hier auch unter Berücksichtigung der versendeten Orientierungskopie faktisch gar nicht möglich gewesen, innert der von der Staatsanwaltschaft berechneten Frist Einsprache zu erheben. Die Strafgerichtspräsidentin sei mit Recht zum Schluss gekommen, dass das Vorgehen der Staatsanwaltschaft unzulässig war und der Strafbefehl daher nichtig sei.
Aber selbst wenn im vorliegenden Fall eine fristgerechte Einsprache für den Beschuldigten faktisch möglich gewesen wäre, ändere dies nichts an der Rechtswidrigkeit des Vorgehens der Staatsanwaltschaft. Auf dem Formular werde die beschuldigte Person zwar darauf hingewiesen, dass Rechtsmittelfristen bereits mit der Zustellung von Entscheiden der Strafbehörden an ein (gewähltes) Zustellungsdomizil zu laufen begännen. Auf dem Formular werde jedoch nicht erwähnt, dass die Einsprachefrist gegen einen allfälligen Strafbefehl lediglich zehn Tage betrage. Das verwendete Formular weise noch weitere Unklarheiten und Mängel auf, und das prozessuale Vorgehen der Staatsanwaltschaft habe die Einsprachefrist zum Nachteil des Beschuldigten zumindest erheblich verkürzt. Im Zeitpunkt der Unterzeichnung des Formulars habe dem Beschuldigten die Tragweite seiner Erklärung offensichtlich nicht bewusst gewesen sein können. Eine rechtzeitige ausreichende Aufklärung durch die Schweizer Behörden sei nicht erfolgt. Damit könne das Verfahren auch nicht mehr als "fair" im Sinne von Art. 6 Ziff. 1 EMRK eingestuft werden.
Zwar könne es auch gewisse Fälle geben, bei denen ein Strafbefehl nach <ref-law> grundsätzlich auch ohne öffentliche Publikation als zugestellt gelten könnte. Nach der Gerichtspraxis (bzw. gemäss <ref-law>) setze dies jedoch voraus, dass die Staatsanwaltschaft zuvor alle Anstrengungen unternommen haben müsste, um den Aufenthaltsort der beschuldigten Person ausfindig zu machen. Dabei sei auch der Möglichkeit einer internationalen Ausschreibung zur Aufenthaltsnachforschung (vgl. <ref-law>) Rechnung zu tragen oder, im Falle einer Wiedereinreise der beschuldigten Person in die Schweiz, der Möglichkeit einer polizeilichen Eröffnung von amtlichen Dokumenten. Falls die ausländische Adresse der beschuldigten Person hingegen bekannt ist oder eruiert werden kann, dürfe auch ein Rückgriff auf Art. 88 Abs. 4 (i.V.m. Art. 88 Abs. 1 lit. c) StPO nicht der Umgehung des Rechtshilfeweges dienen; vielmehr habe in diesen Fällen eine rechtshilfeweise Eröffnung des Strafbefehls zu erfolgen. Erst wenn seitens der Staatsanwaltschaft alle zumutbaren Anstrengungen erfolglos unternommen wurden, komme subsidiär noch eine Zustellung mittels Eröffnung des Straferkenntnisses im kantonalen Amtsblatt in Frage.
2.2. Die Staatsanwaltschaft vertritt in der Beschwerdeschrift (zusammengefasst) folgenden Standpunkt:
Das fragliche Formular ("Erklärung betreffend Zustellungsdomizil in der Schweiz") der Strafbefehlsabteilung der Staatsanwaltschaft gelange seit Mitte Oktober 2018 zur Anwendung. Es werde analog auch im Kanton St. Gallen benutzt. Dem Beschuldigten sei eine englischsprachige Fassung zur Unterschrift vorgelegt worden. Darauf sei unter anderem vermerkt, dass mit der Zustellung von Entscheiden der Strafbehörden an das gewählte Zustellungsdomizil in der Schweiz die Rechtsmittelfristen zu laufen begännen. Mit dem Beschuldigten hätten die Organe des Grenzwachtkorps Englisch gesprochen; auch Korrespondenz sei mit ihm in dieser Sprache geführt worden. Dabei habe er auch zum Ausdruck gebracht, dass er mit dem strafrechtlichen Vorwurf nicht einverstanden sei. Weder den Inhalt des drei Monate später gegen ihn erlassenen Strafbefehls, noch die Art und Höhe einer allfälligen Sanktion habe er damals kennen können. Der Beschuldigte spreche aber offenbar gut Englisch und habe die Angaben auf dem Formular und die mündlich abgegebenen Erläuterungen zweifellos verstanden. Gestützt auf das von ihm unterzeichnete Formular sei ihm der Strafbefehl durch Zustellung an das gewählte Domizil bei der Staatsanwaltschaft rechtsgültig eröffnet worden.
Zum Einwand des Appellationsgerichtes, im vorliegenden Fall sei durch das Vorgehen der Staatsanwaltschaft das Einspracherecht des Beschuldigten gegen den Strafbefehl faktisch vereitelt worden, bringt diese vor, sie habe in dieser Situation "nicht als staatliches Organ der Strafverfolgung" gehandelt, sondern lediglich als "eine von der beschuldigten Person beauftragte Domizilhalterin". Die lange Übermittlungsdauer der an den ausländischen Wohnsitz des Beschuldigten versendeten Orientierungskopie habe allein in dessen Risikobereich gelegen und könne nicht ihr, der Staatsanwaltschaft, angelastet werden.
Die Staatsanwaltschaft rügt in diesem Zusammenhang eine falsche Anwendung von Bundesrecht, insbesondere von <ref-law>.
3.
3.1. Jede Person hat bei Rechtsstreitigkeiten Anspruch auf Beurteilung durch eine richterliche Behörde (<ref-law>). Jede verurteilte Person hat das Recht, das Strafurteil von einem höheren Gericht überprüfen zu lassen (<ref-law>). Die beschuldigte Person muss auch die Möglichkeit haben, die ihr zustehenden Verteidigungsrechte geltend zu machen (<ref-law>). Analoge grundrechtliche Garantien ergeben sich auch aus Art. 6 Ziff. 1 EMRK.
Entscheide, in denen über Straf- und Zivilfragen materiell befunden wird, ergehen in Form eines Urteils. Die anderen Entscheide ergehen, wenn sie von einer Kollektivbehörde gefällt werden, in Form eines Beschlusses, wenn sie von einer Einzelperson gefällt werden, in Form einer Verfügung. Die Bestimmungen des Strafbefehlsverfahrens bleiben vorbehalten (<ref-law>). Die beschuldigte Person kann gegen einen Strafbefehl innert 10 Tagen bei der Staatsanwaltschaft schriftlich Einsprache erheben (<ref-law>). Ohne gültige Einsprache wird der Strafbefehl zum rechtskräftigen Urteil (<ref-law>).
Beim Strafbefehl handelt es sich nach der Praxis des Bundesgerichtes um einen Vorschlag zur aussergerichtlichen Erledigung der Strafsache. Die Einsprache gegen den Strafbefehl ist kein Rechtsmittel (im Sinne von Art. 379-415 StPO), sondern ein Rechtsbehelf, der das gerichtliche Verfahren auslöst, in dem über die Berechtigung der im Strafbefehl enthaltenen Deliktsvorwürfe entschieden wird. Die einspracheberechtigte Person darf und muss auf ein rechtsstaatliches Strafbefehlsverfahren vertrauen können. Die Staatsanwaltschaft trägt in diesem Verfahrensabschnitt die Verantwortung für die Einhaltung der "Grundsätze des Verfahrensrechts". Auf den grundrechtlich garantierten gerichtlichen Rechtsschutz (Art. 29a i.V.m. <ref-law>) kann nur der ausreichend informierte Beschuldigte wirksam verzichten (<ref-ruling> E. 2.6 S. 86).
Die zehntägige Einsprachefrist beginnt einen Tag nach der Mitteilung des Strafbefehls zu laufen (Art. 90 Abs. 1 i.V.m. <ref-law>). Die Frist ist eingehalten, wenn die Einsprache spätestens am letzten Tag der Frist bei der Staatsanwaltschaft eintrifft oder die betreffende schriftliche Eingabe zu Handen der Staatsanwaltschaft am letzten Tag der Frist der Schweizerischen Post, einer schweizerischen diplomatischen oder konsularischen Vertretung oder, im Falle von inhaftierten Personen, der Anstaltsleitung übergeben wird (<ref-law>).
Die Strafbehörden bedienen sich für ihre Mitteilungen der Schriftform, soweit die StPO nichts Abweichendes bestimmt (<ref-law>). Die Zustellung erfolgt durch eingeschriebene Postsendung oder auf andere Weise gegen Empfangsbestätigung, insbesondere durch die Polizei (<ref-law>). Mit dem Einverständnis der betroffenen Person können Mitteilungen elektronisch zugestellt werden; sie sind mit einer elektronischen Signatur zu versehen (<ref-law>). Mitteilungen sind den Adressatinnen und Adressaten an ihren Wohnsitz, ihren gewöhnlichen Aufenthaltsort oder an ihren Sitz zuzustellen (<ref-law>). Parteien und Rechtsbeistände mit Wohnsitz, gewöhnlichem Aufenthaltsort oder Sitz im Ausland haben in der Schweiz ein Zustellungsdomizil zu bezeichnen; vorbehalten bleiben staatsvertragliche Vereinbarungen, wonach Mitteilungen direkt zugestellt werden können (<ref-law>; s.a. <ref-ruling>; <ref-ruling>).
Die Zustellung erfolgt gemäss <ref-law> durch Veröffentlichung in dem durch den Bund oder den Kanton bezeichneten Amtsblatt, wenn (lit. a) der Aufenthaltsort der Adressatin oder des Adressaten unbekannt ist und trotz zumutbarer Nachforschungen nicht ermittelt werden kann, (lit. b) eine Zustellung unmöglich ist oder mit ausserordentlichen Umtrieben verbunden wäre, oder (lit. c)eine Partei oder ihr Rechtsbeistand mit Wohnsitz, gewöhnlichem Aufenthaltsort oder Sitz im Ausland kein Zustellungsdomizil in der Schweiz bezeichnet hat. Einstellungsverfügungen und Strafbefehle gelten auch ohne Veröffentlichung als zugestellt (<ref-law>). Wer berechtigt ist, ein Rechtsmittel zu ergreifen, kann nach Eröffnung des anfechtbaren Entscheids durch schriftliche oder mündliche Erklärung gegenüber der entscheidenden Behörde auf die Ausübung dieses Rechts verzichten (<ref-law>).
3.2. Straferkenntnisse stellen staatliche Hoheitsakte dar, die gegenüber Parteien mit Wohnsitz im Ausland grundsätzlich auf dem Wege der internationalen Rechtshilfe in Strafsachen förmlich zu eröffnen sind (vgl. Art. 63 Abs. 2 lit. a i.V.m. Art. 68 und Art. 77 IRSG). In der Schweiz dürfen ausländische Schriftstücke - mangels anderer staatsvertraglicher Regelung - nur an Personen unmittelbar mit der Post zugestellt werden, die im ausländischen Staat nicht selber verfolgt werden; ausgenommen auch von dieser direkten Zustellung sind Vorladungen (<ref-law>). Eine unmittelbare postalische Zustellung an Personen mit Wohnsitz in der Schweiz erlaubt das Schweizer Recht ferner für ausländische Schriftstücke in Strafsachen wegen Übertretung von Strassenverkehrsvorschriften (<ref-law>).
3.3. Eine Ausnahme vom Erfordernis der rechtshilfeweisen Eröffnung von Straferkenntnissen auf dem Weg der Rechtshilfe bzw. des diplomatischen Verkehrs liegt vor, wenn zwischen der Schweiz und dem betroffenen ausländischen Staat eine (multi- oder bilaterale) völkerrechtliche Vereinbarung besteht, die eine vereinfachte direkte Zustellung von Straferkenntnissen an die im Ausland wohnhaften Parteien auf dem postalischen Wege zulässt (<ref-ruling> E. 5.1 S. 305 mit Hinweis; <ref-ruling> E. 3a S. 50; Urteil 1C_236/2016 vom 15. November 2016 E. 3.2; s.a. <ref-ruling> E. 2.2.1 S. 32; <ref-ruling> E. 2.4 S. 89-91; <ref-ruling> E. 2.2 S. 625-627; nicht amtl. publ. E. 3.2 von <ref-ruling>; vgl. Sararard Arquint, in: Basler Kommentar Internationales Strafrecht, 2015, <ref-law> N. 1-7; Robert Zimmermann, La coopération judiciaire internationale en matière pénale, 5. Aufl., Bern 2019, Rz. 382). Nur im Geltungsbereich solcher staatsvertraglicher Regelungen kann sowohl auf die rechtsgültige Vereinbarung eines Zustelldomizils in der Schweiz (<ref-law>) verzichtet werden, als auch auf eine rechtshilfeweise Eröffnung des Straferkenntnisses (vgl. Sararard Arquint, in: Basler Kommentar StPO, 2. Aufl. 2014, Art. 87 N. 4; Brüschweiler/Nadig/Schneebeli, in: Zürcher Kommentar StPO, 3. Aufl. 2020, Art. 87 N. 2, 4). Eine unzulässige direkte postalische Zustellung begründet im Lichte des Völkerrechts einen Eröffnungsmangel (nicht amtl. publ. E. 3.2 von <ref-ruling>). Wird ein Strafbefehl an einen im Ausland domizilierten Beschuldigten fehlerhaft zugestellt, beginnt die Einsprachefrist von <ref-law> erst nach rechtsgültiger Zustellung zu laufen (vgl. Gilliéron/Killias, in: Commentaire Romand CPP, 2. Aufl., Basel 2019, Art. 354 N. 12).
Der Vertrag vom 12. Mai 2004 zwischen der Schweizerischen Eidgenossenschaft und der Föderativen Republik Brasilien über Rechtshilfe in Strafsachen (RV-BRA, SR 0.351.919.81) sieht für die förmliche Eröffnung von Verfahrensurkunden und Gerichtsentscheidungen in Strafsachen im jeweils anderen Staat ausschliesslich den Rechtshilfeweg vor (Art. 14 Ziff. 1 RV-BRA). Eine direkte postalische Zusendung von Straferkenntnissen an Parteien mit Wohnsitz im anderen Vertragsstaat (mit fristauslösenden Wirkungen) haben Brasilien und die Schweiz nicht vereinbart.
Zu prüfen bleibt, ob im vorliegenden Fall eine fristauslösende Zustellung des Strafbefehls ohne rechtshilfeweise Eröffnung, schon gestützt auf das innerstaatliche Strafprozessrecht, rechtsgültig erfolgen konnte.
3.4. Unbestrittenermassen war der Staatsanwaltschaft im Zeitpunkt des Erlasses ihres Strafbefehls am 9. April 2019 die Wohnadresse des Beschuldigten in Brasilien bekannt. Wie die Vorinstanz gestützt auf die Akten darlegt, kam die per Einschreiben an diese Wohnadresse versendete "Orientierungskopie" erst am 17. April 2019 an der brasilianischen Grenzkontrollstelle an. In diesem Zeitpunkt wären - nach Ansicht der Staatsanwaltschaft - bereits acht Tage der zehntägigen Einsprachefrist verstrichen gewesen. Wie die Vorinstanz nachvollziehbar darlegt, wäre es dem Beschuldigten faktisch kaum möglich gewesen, die ihm postalisch zugestellte "Orientierungskopie" innert nützlicher Frist zur Kenntnis zu nehmen und gestützt darauf noch fristgerecht eine (auch im Lichte von Art. 90 Abs. 1 und <ref-law>) gültige schriftliche Einsprache gegen den Strafbefehl zu erheben. Das Appellationsgericht weist zudem darauf hin, dass der Beschuldigte (anlässlich seiner Befragung durch die Schweizer Grenzwache) den vorgehaltenen Sachverhalt nicht anerkannte, weshalb die Staatsanwaltschaft mit einiger Wahrscheinlichkeit damit habe rechnen müssen, dass der Beschuldigte sein Einspracherecht würde ausüben wollen. Bei dieser konkreten Sachlage interpretiert die Staatsanwaltschaft die - für einen juristischen Laien nicht leicht durchschaubaren - Angaben auf ihrem Formular "Erklärung betreffend Zustellungsdomizil in der Schweiz" hier als faktischen Verzicht des Beschuldigten auf eine wirksame Einsprache gegen den Strafbefehl.
Als zutreffend erweist sich die Ansicht der kantonalen Gerichte, dass eine die Einsprachefrist von <ref-law> auslösende Eröffnung des Strafbefehls in Fällen wie dem vorliegenden weder mittels amtlicher Publikation im Kantonsblatt (<ref-law>) erfolgen kann, noch über eine per Polizeiformular bewirkte Fiktion einer Zustellung an ein schweizerisches "Wahldomizil" bei der Staatsanwaltschaft (vgl. <ref-law>).
Die Auffassung der kantonalen Gerichte, dass der Strafbefehl hier dem Beschuldigten auf dem Rechtshilfeweg an seiner den Strafbehörden bekannten Wohnadresse im Ausland zu eröffnen ist und die Einsprachefrist erst ab dieser gültigen Zustellung läuft, hält vor dem Bundesrecht stand. Im vorliegenden Fall erscheint es zumindest fraglich, ob der Beschuldigte in ausreichender Kenntnis der rechtlichen Konsequenzen ein Schweizer Zustelldomizil für Straferkenntnisse bei der Staatsanwaltschaft gewählt und damit faktisch auf ein wirksames Einspracherecht verzichtet hat:
Das hier verwendete Formular nennt die kurze zehntägige Einsprachefrist von <ref-law> nicht. Ebenso wenig wird ausgeführt, dass der im Formular verwendete Begriff "Rechtsmittelfrist" nicht nur für die gesetzlich genannten Rechtsmittel gelte (Art. 379-415 StPO; vgl. insbes. <ref-law> betreffend "Verzicht" auf Rechtsmittel), sondern - nach der Interpretation der Staatsanwaltschaft - auch noch für den separat geregelten Rechtsbehelf der Einsprache gegen Strafbefehle (vgl. dazu <ref-ruling> E. 2.6 S. 86). Wie die Vorinstanz zutreffend erwähnt, wird die beschuldigte Person im Formular auch nicht darüber aufgeklärt, wie es sich mit den Modalitäten betreffend Fristenwahrung aus dem Ausland verhält bzw. auf welchem Weg die beschuldigte Person im Falle der Wahl eines Zustellungsdomizils bei der Staatsanwaltschaft die sehr kurze Einsprachefrist gegen Strafbefehle wirksam wahren könnte.
Der Vorinstanz ist ebenso darin zuzustimmen, dass das Formular - entgegen dem Standpunkt der Staatsanwaltschaft - der beschuldigten Person keine Wahl lässt, auf ein Zustelldomizil in der Schweiz zu verzichten. Das Formular erlaubt der verzeigten Person lediglich die Wahl eines Zustelldomizils, und zwar (als Alternativen) entweder bei der Staatsanwaltschaft oder bei einer von der verzeigten Person frei gewählten Privatperson mit Wohnsitz in der Schweiz. Der im Formular eingangs noch vorbehaltene Fall einer staatsvertraglich vereinbarten direkten Zustellung von Mitteilungen auf dem postalischen Weg liegt hier nicht vor. Die durchaus naheliegende Variante einer rechtshilfeweisen Zustellung von Straferkenntnissen am bereits bekannten ausländischen Wohndomizil der beschuldigten Person, wie sie etwa im Verkehr mit Brasilien völkerrechtlich vereinbart ist, wird im Formular überhaupt nicht erwähnt. Dieses beschränkt ein gewähltes Zustelldomizil auch nicht auf Strafbefehle, sondern erstreckt sich nach seinem Wortlaut auf sämtliche Straferkenntnisse ("Entscheide der Strafbehörden"/"Rechtsmittelfristen").
Unbestritten ist schliesslich, dass dem aus Brasilien stammenden Beschuldigten (mit Wohnsitz in Sao Paulo) kein Formular in seiner Muttersprache (Portugiesisch) übergeben wurde. Nach Angaben der Staatsanwaltschaft ist ihr Formular lediglich auf Albanisch, Englisch, Französisch, Italienisch, Rumänisch, Serbisch, Spanisch und Türkisch erhältlich. Die Ansicht der Staatsanwaltschaft, der Beschuldigte habe die - für einen juristischen Laien anspruchsvollen - Ausführungen auf dem englischsprachigen Formular und die von den Grenzwächtern auf Englisch gemachten mündlichen Rechtsbelehrungen "zweifellos" verstanden, ist daher sachlich nur schwer nachvollziehbar.
3.5. Die von der Staatsanwaltschaft favorisierte generelle Standardformular-Lösung mit Zustellfiktion mag zwar aus ihrer Sicht durchaus verfahrenseffizient erscheinen. Sie widerspricht aber im vorliegenden Fall den bundesrechtlichen Vorschriften zum Schutz der Parteirechte von beschuldigten Personen (<ref-law> i.V.m. Art. 29a und Art. 32 Abs. 2-3 BV) sowie den einschlägigen völkerrechtlichen Verpflichtungen der Schweiz (Art. 14 Ziff. 1 i.V.m. Art. 1 Ziff. 1-3 RV-BRA und <ref-law>). Der Ansicht der Staatsanwaltschaft, sie habe in der betreffenden Phase des Strafbefehlsverfahrens "nicht als staatliches Organ der Strafverfolgung" gewirkt, sondern lediglich als eine von der beschuldigten Person beauftragte "Domizilhalterin", widerspricht der oben (E. 3.1) dargelegten einschlägigen Praxis des Bundesgerichtes (<ref-ruling> E. 2.6 S. 86).
Die Auffassung der kantonalen Gerichte, die Wahl eines Schweizer Zustellungsdomizils sei hier nicht rechtswirksam erfolgt, weshalb der Strafbefehl neu auszufertigen und dem Beschuldigten auf dem Rechtshilfeweg zu eröffnen ist, hält vor dem Bundesrecht stand. In diesem Zusammenhang ist auch der Gerichtspraxis angemessen Rechnung zu tragen, wonach nur ausreichend informierte beschuldigte Personen auf ihren verfassungsmässig garantierten gerichtlichen Rechtsschutz gegen Straferkenntnisse wirksam verzichten können (<ref-ruling> E. 2.6 S. 86; Urteil des Bundesgerichtes 6B_152/2013 vom 27. Mai 2013 E. 4.3-4.4; vgl. Richard Calame, CR CPP [a.a.O.], Art. 386 N. 2; Viktor Lieber, ZHK StPO [a.a.O.], Art. 386 N. 1; Schmid/ Jositsch, Praxiskommentar StPO, 3. Aufl., Zürich 2018, Art. 386 N. 1; Christian Schwarzenegger, ZHK StPO, Art. 354 N. 7; Marc Thommen, Kurzer Prozess - fairer Prozess? Strafbefehls- und abgekürztes Verfahren zwischen Effizienz und Gerechtigkeit, Bern 2013, S. 303 ff.). Ein eigentlicher Verzicht wäre im Übrigen erst nach formgültiger Eröffnung des anfechtbaren Entscheides zulässig (<ref-law>). Dies gilt analog auch für den Rechtsbehelf der Einsprache gegen Strafbefehle (vgl. Gilliéron/Killias, CR CPP, Art. 354 N. 5; Schwarzenegger, a.a.O, Art. 354 N. 7; Ziegler/Keller, BSK StPO [a.a.O.], Art. 386 N. 1).
4.
Die Beschwerde ist abzuweisen.
Es sind keine Gerichtskosten zu erheben (<ref-law>), und es ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, und A._, Sao Paulo, schriftlich mitgeteilt.
Lausanne, 12. Mai 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kneubühler
Der Gerichtsschreiber: Forster