Sachverhalt:
A.
Die A._ AG verdächtigte X._, am 5. Mai 2018 Fr. 541.70 der Tageseinnahmen entwendet und für eigene Zwecke gebraucht zu haben und erstattete am 12. Juni 2018 Strafanzeige wegen Diebstahls. Die Staatsanwaltschaft sprach am 4. September 2018 mittels Strafbefehl eine bedingte Geldstrafe von 30 Tagessätzen zu Fr. 30.- gegen X._ aus. Der Strafbefehl erwuchs wegen verspäteter Einsprache in Rechtskraft.
Am 26. Oktober 2018 teilte die A._ AG den Strafverfolgungsbehörden mit, sie ziehe ihre Strafanzeige zurück, da eine Prüfung durch die Buchhaltung ergeben habe, dass der Strafanzeige ein Berechnungsfehler zugrunde lag und kein Geld entwendet wurde.
Mit Beschluss vom 29. Mai 2019 trat das Obergericht des Kantons Aargau auf ein von der Staatsanwaltschaft zugunsten von X._ gestelltes (zweites) Revisionsgesuch nicht ein.
B.
X._ beantragt mit Beschwerde in Strafsachen, der Strafbefehl vom 4. September 2018 sei in Gutheissung des Revisionsgesuchs der Staatsanwaltschaft aufzuheben und er sei vom Vorwurf des Diebstahls freizusprechen bzw. das Strafverfahren sei einzustellen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Obergericht beantragt in seiner Stellungnahme, die Beschwerde sei kostenfällig abzuweisen, soweit darauf einzutreten sei. Die Oberstaatsanwaltschaft verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von <ref-law>. Die Vorinstanz sei trotz Vorliegens eines Revisionsgrundes nicht auf das Revisionsgesuch der Staatsanwaltschaft eingetreten. Das Schreiben der A._ AG, mit der diese ihre Strafanzeige zurückgezogen habe, belege, dass kein Geld entwendet worden sei und er keinen Diebstahl begangen habe. Er habe zwar im gesamten Verfahren den ihm zur Last gelegten Diebstahl bestritten, vom Berechnungsfehler und dem darauf basierenden Irrtum der A._ AG habe er jedoch keine Kenntnis gehabt. Der Rechenfehler sei erst nach Erlass des Strafbefehls aufgedeckt worden, weshalb er diesen auch nicht vor Ablauf der Einsprachefrist hätte geltend machen können.
1.2. Die Vorinstanz erwägt zusammengefasst, das Strafbefehlsverfahren verlange, dass die beschuldigte Person zum Strafbefehl Stellung nehme, indem sie diesen entweder in Rechtskraft erwachsen lasse, wenn sie mit ihm einverstanden sei, oder Einsprache erhebe, wenn sie eine Verurteilung nicht anerkenne. Gemäss bundesgerichtlicher Rechtsprechung sei ein Revisionsgesuch als rechtsmissbräuchlich zu qualifizieren, wenn darin Tatsachen geltend gemacht würden, die der verurteilten Person von Anfang an bekannt waren und die sie im ordentlichen Verfahren hätte geltend machen können. Das Revisionsverfahren sei kein Ersatz für das ordentliche Rechtsmittelverfahren, auf das der Beschwerdeführer verzichtet habe. Im Falle fristgerechter Einsprache hätte das erstinstanzliche Gericht nach Abnahme und Würdigung der Beweise beurteilen können, ob hinsichtlich des dem Beschwerdeführer gemachten Vorwurfs ein rechtsgenügend erstellter Sachverhalt vorgelegen habe. Dass die A._ AG ihre Strafanzeige später zurückgezogen habe, sei unerheblich, da dies nicht kausal für das Bestreiten der gegen ihn erhobenen Vorwürfe gewesen sei. Der Beschwerdeführer habe nach seinem eigenen Vorbringen ja gewusst, keinen Diebstahl begangen zu haben. Vielmehr habe er es sich selber zuzuschreiben, dass er nicht innert Frist Einsprache erhoben habe, und könne im Wege der Revision nicht nachholen, was er im ordentlichen Rechtsmittelverfahren verpasst habe. Ein derartiges Verhalten verdiene keinen Rechtsschutz, sondern sei als rechtsmissbräuchlich zu qualifizieren. Dies gelte auch dann, wenn die Staatsanwaltschaft zu seinen Gunsten ein Revisionsgesuch gestellt habe.
2.
Gemäss <ref-law> kann, wer durch ein rechtskräftiges Urteil,einen Strafbefehl, einen nachträglichen richterlichen Entscheid oder einen Entscheid im selbstständigen Massnahmeverfahren beschwert ist, die Revision verlangen, wenn neue, vor dem Entscheid eingetretene Tatsachen oder neue Beweismittel vorliegen, die geeignet sind, einen Freispruch, eine wesentlich mildere oder wesentlich strengere Bestrafung der verurteilten Person oder eine Verurteilung der freigesprochenen Person herbeizuführen.
Die Revision ist zuzulassen, wenn die Abänderung des früheren Urteils wahrscheinlich erscheint. Sie dient hingegen nicht dazu, rechtskräftige Entscheide jederzeit infrage zu stellen oder frühere prozessuale Versäumnisse zu beheben. Ein Gesuch um Revision eines Strafbefehls muss als missbräuchlich qualifiziert werden, wenn es sich auf Tatsachen stützt, die der verurteilten Person von Anfang an bekannt waren, die sie ohne schützenswerten Grund verschwieg und die sie in einem ordentlichen Verfahren hätte geltend machen können, welches auf Einsprache hin eingeleitet worden wäre. Demgegenüber kann die Revision eines Strafbefehls in Betracht kommen wegen wichtiger Tatsachen oder Beweismittel, die die verurteilte Person im Zeitpunkt, als der Strafbefehl erging, nicht kannte oder die schon damals geltend zu machen für sie unmöglich waren oder keine Veranlassung bestand. Rechtsmissbrauch ist nur mit Zurückhaltung anzunehmen. Es ist in jedem Einzelfall zu prüfen, ob unter den gegebenen Umständen das Revisionsgesuch dazu dient, den ordentlichen Rechtsweg zu umgehen (zum Ganzen: 6B_517/2018 vom 24. April 2019 E. 1.1, zur Publ. bestimmt; mit Nachweisen).
3.
3.1. Die Vorinstanz tritt auf das Revisionsgesuch der Staatsanwaltschaft wegen offensichtlicher Unzulässigkeit mit der Begründung nicht ein, das Prozessverhalten des Beschwerdeführers sei rechtsmissbräuchlich und verdiene keinen Rechtsschutz. Unklar ist, welches Verhalten des Beschwerdeführers im Revisionsverfahren die Vorinstanz als rechtsmissbräuchlich qualifiziert, da dieser sich gemäss ihrer eigenen Erwägungen "am Revisionsbegehren, das von der Staatsanwaltschaft zu seinen Gunsten erhoben worden ist, nicht aktiv beteiligt" hat. Ob und inwieweit das Revisionsgesuch der Staatsanwaltschaft aufgrund der verspäteten Einsprache des Beschwerdeführers rechtsmissbräuchlich und damit offensichtlich unzulässig im Sinne von <ref-law> sein kann, erscheint fraglich, zumal Rechtsmissbrauch nur mit Zurückhaltung anzunehmen ist (vorstehend E. 2). Wie es sich damit im Einzelnen verhält, kann vorliegend offenbleiben, denn das Revisionsgesuch erweist sich selbst dann nicht als rechtsmissbräuchlich, wenn das beanstandete Prozessverhalten des Beschwerdeführers der Staatsanwaltschaft zuzurechnen ist.
3.2.
3.2.1. Die Vorinstanz weist zutreffend darauf hin, dass gemäss gefestigter bundesgerichtlicher Rechtsprechung ein Revisionsgesuch (der verurteilten Person) grundsätzlich als rechtsmissbräuchlich zu qualifizieren ist, wenn es sich auf Tatsachen stützt, die der verurteilten Person von Anfang an bekannt waren und die sie in einem ordentlichen Verfahren hätte geltend machen können. Diese Voraussetzungen sind vorliegend jedoch nach den verbindlichen vorinstanzlichen Feststellungen nicht erfüllt, denn weder die Staatsanwaltschaft noch der Beschwerdeführer wussten im Zeitpunkt des Erlasses des Strafbefehls, dass der von der A._ AG zur Anzeige gebrachte Lebenssachverhalt auf einem Rechenfehler beruhte. Dieser wurde auch erst nach mehrfacher Prüfung durch die Buchhaltung der Anzeigeerstatterin aufgedeckt und mitgeteilt, als der Strafbefehl bereits (unangefochten) in Rechtskraft erwachsen war. Mangels Kenntnis hätte der Beschwerdeführer diese Umstände - wie auch die gesuchstellende Staatsanwaltschaft - nicht im Rahmen eines auf fristgerechte Einsprache hin durchgeführten erstinstanzlichen Verfahrens geltend machen können. Insofern ist auch im Lichte der von der Vorinstanz zitierten bundesgerichtlichen Rechtsprechung nicht ersichtlich, inwieweit die Geltendmachung dieser Tatsachen und Beweismittel, insbesondere durch die Staatsanwaltschaft, rechtsmissbräuchlich sein soll.
Soweit die Vorinstanz ausführt, dass das erstinstanzliche Gericht auf Einsprache des Beschwerdeführers allfällige Beweise hätte abnehmen und mit freier Kognition darüber hätte entscheiden können, ob der Anklagevorwurf erstellt gewesen wäre, ändert dies nichts daran, dass die Staatsanwaltschaft und der Beschwerdeführer im Zeitpunkt des Eintritts der Rechtskraft des Strafbefehls von den im Revisionsverfahren geltend gemachten neuen Tatsachen und Beweisen keine Kenntnis hatten. Auch wenn das Strafbefehlsverfahren ein besonderes (vereinfachtes) Verfahren ist (vgl. <ref-law>), entbindet dies die Staatsanwaltschaft nicht von ihrer Aufgabe, in der Untersuchung den Sachverhalt tatsächlich und rechtlich so weit abzuklären, dass sie das Vorverfahren abschliessen kann (<ref-law>). Ein Strafbefehl kann nur erlassen werden, wenn der Sachverhalt eingestanden oder anderweitig ausreichend geklärt ist (<ref-law>), zumal er - soweit die Staatsanwaltschaft nach Einsprache an ihm festhält - als Anklageschrift dient (<ref-law>). Der Untersuchungsgrundsatz (<ref-law>) gelangt im gesamten Strafverfahren und nicht erst ab dem erstinstanzlichen Gerichtsverfahren zur Anwendung.
3.2.2. Die Vorinstanz scheint davon auszugehen, dass ein Revisionsgesuch gegen einen Strafbefehl nur dann nicht rechtsmissbräuchlich ist, wenn die verurteilte Person hiergegen zuvor form- und fristgerecht Einsprache erhoben hat. Dies widerspricht der von ihr zitierten bundesgerichtlichen Rechtsprechung und dem eindeutigen Wortlaut von <ref-law>. Würde man der Ansicht der Vorinstanz folgen, wäre eine Revision gegen einen Strafbefehl (faktisch) ausgeschlossen, da dieser bei fristgerechter und formgültiger Einsprache nicht in Rechtskraft erwachsen würde, was aber unabdingbare Voraussetzung für eine Revision ist. Ob der Strafbefehl (oder das Urteil, der nachträgliche richterliche oder der im selbstständigen Massnahmeverfahren ergangene Entscheid) in Rechtskraft erwächst, weil die beschwerte Person die Rechtsmittelfrist unbenützt ablaufen lässt, auf ein Rechtsmittel verzichtet oder dieses zurückzieht oder die Rechtsmittelinstanz auf das Rechtsmittel nicht eintritt oder es abweist, spielt im Hinblick auf die Rechtskraft und die Möglichkeit einer Revision des Entscheids keine Rolle (vgl. Art. 410 Abs. 1 i.V.m. <ref-law>).
Entgegen der Vorinstanz eröffnet die Revision gegen einen Strafbefehl ohne gültige Einsprache der beschuldigten Person (oder wie vorliegend der Staatsanwaltschaft) auch nicht die Möglichkeit, das Revisionsgesuch nach Belieben wegen Tatsachen zu verlangen, die die gesuchstellende Partei bereits im ordentlichen Verfahren hätte vorbringen können. Derartige Vorbringen stellen - wie bei Urteilen oder anderen verfahrensabschliessenden Entscheiden auch - gerade keinen Revisionsgrund dar (vgl. <ref-law>; Urteil 6B_517/2018 vom 24. April 2019 E. 1.1). Soweit die Vorinstanz ausführt, der Beschwerdeführer könne sich nicht auf den Berechnungsfehler und den Rückzug der Strafanzeige durch die A._ AG berufen, da diese Umstände nicht kausal dafür gewesen seien, dass er den Diebstahlsvorwurf bestritten hat, lässt sich damit das Revisionsgesuch nicht abweisen, sondern stellt den zulässigen Revisionsgrund dar. Nur wenn der Beschwerdeführer von diesen Umständen im Vorverfahren bereits Kenntnis gehabt und seine Täterschaft damit verneint hätte, hätte er sein Revisionsgesuch damit nicht mehr begründen können. Dass er den Diebstahl bestritten und nach seiner "Sichtweise" gewusst hat, diesen nicht begangen zu haben, liegt bei einer zu Unrecht verurteilten Person in der Natur der Sache und konnte im Übrigen den Erlass des Strafbefehls nicht verhindern. Auch begründet die Staatsanwaltschaft das Revisionsgesuch gerade nicht mit der Kenntnis des Beschwerdeführers von dessen Unschuld, sondern mit dem ihr (und ihm) seinerzeit nicht bekannten Rechenfehler, der zum Rückzug der Strafanzeige geführt hat. Insofern ist nicht ersichtlich, inwiefern das Prozessverhalten der Staatsanwaltschaft und des Beschwerdeführers dazu dienen soll, den ordentlichen Rechtsweg zu umgehen.
4.
Die Beschwerde erweist sich als begründet. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (<ref-law>). Der vor Bundesgericht nicht anwaltlich vertretene Beschwerdeführer macht keine Aufwendungen geltend und ist demnach für das bundesgerichtliche Verfahren nicht zu entschädigen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Aargau vom 29. Mai 2019 aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 19. August 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held