Sachverhalt:
A.
A.a. X._ beriet als Kundenbetreuer der Bank B._ AG A._ in Anlagefragen. Aufgrund einer Streitigkeit betreffend eine Überweisung von EUR 160'000 zu Lasten des A._ reichte dieser am 11. November 2009 Strafanzeige gegen X._ ein. Nachdem Letzterer eine Schuldanerkennung über EUR 179'137.55 unterzeichnet hatte (Vereinbarung vom 4. Dezember 2009), erklärte A._ am 11. Dezember 2009 - unter der Voraussetzung, dass X._ seinen stipulierten Zahlungsverpflichtungen nachkomme - zu Handen der Staatsanwaltschaft des Kantons Basel-Stadt sein Desinteresse an einer Weiterverfolgung der Strafanzeige. Er habe sich entschieden, zurzeit keine Aussagen zu machen. Die Staatsanwaltschaft stellte das Verfahren am 14. Dezember 2009 mangels Beweises des Tatbestands sowie auf Grund der Desinteresse-Erklärung des A._ formlos ein. Eine Mitteilung an die Parteien erfolgte nicht.
A.b. Am 14. Dezember 2012 reichte A._ erneut Strafanzeige gegen X._ ein, welcher die Vereinbarung vom 4. Dezember 2009 nicht korrekt erfüllt habe. Die Staatsanwaltschaft des Kantons Basel-Stadt erhob am 19. November 2013 Anklage beim Strafgericht des Kantons Basel-Stadt.
B.
Das Strafgericht des Kantons Basel-Stadt sprach X._ am 19. Dezember 2014 des Betrugs schuldig und verurteilte ihn zu einer bedingten Freiheitsstrafe von 15 Monaten.
C.
Die von X._ dagegen erhobene Berufung wies das Appellationsgericht des Kantons Basel-Stadt am 15. September 2016 ab.
D.
X._ führt Beschwerde in Strafsachen. Er beantragt in der Hauptsache, der Entscheid sei aufzuheben und das Verfahren gegen ihn kostenfällig einzustellen. Eventualiter sei von einer Bestrafung abzusehen, subeventualiter die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt vorab, es sei in derselben Sache bereits am 14. Dezember 2009 eine Einstellung erfolgt, womit eine res iudicata vorliege. Es fehle somit an einer Prozessvoraussetzung für ein erneutes Strafverfahren. Zur Begründung führt er im Wesentlichen an, § 110 der damals massgebenden basel-städtischen Strafprozessordnung (nachfolgend: aStPO/BS) habe abschliessend zwei - hier unbestritten nicht vorliegende - Gründe für eine vorläufige Einstellung des Verfahrens genannt. Indem die Vorinstanz darüber hinaus von einem vorläufigen Einstellungsgrund sui generis ausgegangen sei, habe sie das Legalitätsprinzip sowie den Grundsatz der Formstrenge verletzt. Für die Annahme eines definitiv eingestellten Verfahrens spreche zudem, dass die Staatsanwaltschaft das Verfahren unter einem neuen Aktenzeichen weitergeführt bzw. wiederaufgenommen habe. Über die Wiederaufnahme eines eingestellten Verfahrens hätte indessen verfügt werden müssen, was gerade nicht geschehen sei.
1.2. Ob die Staatsanwaltschaft das Verfahren am 14. Dezember 2009 definitiv einstellen wollte - wofür die spätere Verwendung eines neuen Aktenzeichens sowie die Bezeichnung in der Vorgangsliste vom 21. Dezember 2012 ("Erledigungsart: Einstellung formlos") sprechen - oder aber das Verfahren nur vorläufig einstellen wollte, ist nicht von Belang:
Wie der Beschwerdeführer selber einwendet, scheitert die Annahme einer nicht mitteilungsbedürftigen vorläufigen Einstellung des Verfahrens gemäss § 110 aStPO/BS am Fehlen der entsprechenden Voraussetzungen eines vorübergehenden Prozesshindernisses oder einer unbekannten Täterschaft. Für eine darüber hinausgehende vorläufige Einstellung "sui generis", wie sie dem vorinstanzlichen Entscheid zu Grunde gelegt wurde, besteht kein Raum. So war im Dezember 2009 keinesfalls klar, ob überhaupt - und, wenn ja, wann - der Geschädigte zu einer Aussage bereit sein würde. Wie das Bundesgericht in E. 2.5 des Urteils 6B_696/2010 vom 15. Februar 2011 festgehalten hat, steht das in Art. 29 Abs. 1 BV verankerte Beschleunigungsgebot einer solch unbegrenzten Sistierung des Strafverfahrens grundsätzlich entgegen (vgl. auch Urteil 1B_250/2008 vom 13. Mai 2009 E. 5 mit Hinweis auf Robert Hauser/Erhard Schweri/Karl Hartmann, Schweizerisches Strafprozessrecht, 6. Aufl., Basel 2005, § 78 Rz. 13). Dieser Grundsatz verdient im vorliegenden Fall umso mehr Beachtung, als keine Mitteilung betreffend die (vorläufige) Einstellung an den Beschwerdeführer erfolgt war und - anders als im zitierten Urteil 6B_696/2010 - die basel-städtische Prozessordnung in § 110 explizit geregelt hatte, unter welchen Voraussetzungen das kantonale Verfahrensrecht eine nicht mitteilungsbedürftige provisorische Einstellung zulässt.
Entgegen der Beschwerde kann indessen auch nicht von einer definitiven Einstellung des Verfahrens ausgegangen werden, wurde darüber doch unbestritten nicht verfügt. Eine formlose definitive Einstellung des Verfahrens sahen bzw. sehen weder die alte basel-städtische noch die am 1. Januar 2011 in Kraft getretene eidgenössische Strafprozessordnung vor (vgl. dazu § 109 aStPO/BS und Art. 319 ff. StPO). Vielmehr muss die Einstellung des Strafverfahrens durch eine beschwerdefähige, formelle Einstellungsverfügung erfolgen (vgl. § 109 Abs. 2 und 3 aStPO/BS; vgl. auch Urteil 6B_79/2012 vom 13. August 2012 E. 2.5). Es erübrigen sich somit zum Vornherein Weiterungen zum Vorliegen von Gründen für die Wiederaufnahme - worüber im Übrigen ebenfalls hätte verfügt werden müssen - eines durch Einstellungsverfügung rechtskräftig beendeten Verfahrens, vgl. Art. 323 StPO, der auf die Wiederaufnahme eines auch nach altem kantonalen Recht eingestellten Verfahrens Anwendung findet (<ref-ruling> E. 2.3).
1.3. Im Ergebnis verhält es sich nicht anders, als wenn die Staatsanwaltschaft das Verfahren - z.B. aus blosser Nachlässigkeit - nicht an die Hand genommen hätte. Hier wie dort mag dieses Nichthandeln sowohl das in Art. 29 Abs. 1 BV verankerte Beschleunigungsgebot wie auch den Erledigungsgrundsatz gemäss § 25 aStPO/BS verletzen. Es führt indessen nicht ohne Weiteres zu einer (vorläufigen oder definitiven) Einstellung des Verfahrens, sondern kann sich - je nach Schwere - auf das Strafmass auswirken, das hier jedoch unangefochten geblieben ist. Daran ändert auch die Desinteresse-Erklärung des Geschädigten nichts, haben die staatlichen Behörden bei Offizialdelikten doch unabhängig von einer solchen abzuklären, ob in tatsächlicher und rechtlicher Hinsicht eine strafbare Handlung vorliegt (vgl. Urteil 1B_191/2009 vom 29. Juli 2008 E. 5.3 mit Hinweisen). Sowohl bei der ungetreuen Geschäftsführung wie auch beim Betrug handelt es sich um Offizialdelikte, weshalb die Desinteresse-Erklärung keinen Einfluss auf den eigentlichen Verfahrensablauf hat. Dagegen wäre es sowohl dem Beschwerdeführer wie auch dem Geschädigten offen gestanden, eine anfechtbare (Einstellungs-) Verfügung zu verlangen.
2.
2.1. Der Beschwerdeführer rügt weiter, die Vorinstanz habe Art. 53 StGB zu Unrecht nicht angewendet. Er habe zwar das Tatbestandsmerkmal der Arglist stets bestritten, ansonsten aber erwiesenermassen anerkannt, dass er falsch gehandelt habe. Er habe somit sein Fehlverhalten mehrfach eingestanden, was das Zugeständnis des Normverstosses implizit beinhalte.
2.2. Entgegen seinen Einwänden hat der Beschwerdeführer den Normbruch nicht anerkannt, was gemäss bundesgerichtlicher Rechtsprechung (vgl. <ref-ruling> E. 3.4.3) gerade Voraussetzung für eine Anwendung von Art. 53 StGB ist. So hat er noch im vorinstanzlichen Verfahren den ihm vorgeworfenen Sachverhalt mit der Behauptung in Zweifel zu ziehen versucht, der Geschädigte habe ihm den Betrag von EUR 160'000.- bewusst als Vorschuss bzw. als Darlehen bezahlt, um den Anlageverlust bei einem anderen Kunden zu decken. Der Beschwerdeführer stellte sich damals auf den Standpunkt, nach dem Grundsatz "in dubio pro reo" sei diese Darlegung zu seinen Gunsten als durchaus mögliche Version zu werten. Vor Bundesgericht äussert sich der Beschwerdeführer zwar nicht mehr zu dieser von der Vorinstanz als "völlig abwegig" bezeichneten Darlehenstheorie. Indessen bestreitet er nach wie vor das Tatbestandsmerkmal der Arglist. In Anbetracht all dessen kann keine Rede davon sein, der Beschwerdeführer habe den Normbruch anerkannt. Insbesondere genügt dazu die letztinstanzlich geäusserte Einsicht nicht, in irgendeiner Weise falsch gehandelt zu haben. Die Vorinstanz hat kein Bundesrecht verletzt, indem sie von einer Strafbefreiung im Sinne von Art. 53 StGB abgesehen hat.
3.
Die Beschwerde ist abzuweisen. Die Kosten sind dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 Satz 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 4'000.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 30. März 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Williner