Sachverhalt:
A.
Die Staatsanwaltschaft des Kantons Zug führte gegen den deutschen Staatsbürger X._ eine Strafuntersuchung wegen gewerbsmässigen Betrugs und mehrfacher ungetreuer Geschäftsbesorgung. Als dieser seinen Wohnsitz nach Deutschland verlegte, ersuchte die Staatsanwaltschaft des Kantons Zug den Leitenden Oberstaatsanwalt in Köln darum, die Strafverfolgung zu übernehmen. Nach Abtretung der Strafverfolgung an die deutschen Strafverfolgungsbehörden wurde das in Zug anhängige Verfahren sistiert. Der Leitende Oberstaatsanwalt in Köln stellte das Ermittlungsverfahren gegen X._ am 24. August 2012 mangels hinreichenden Tatverdachts ein. Mit Verfügung vom 11. Februar 2015 stellte die Staatsanwaltschaft des Kantons Zug das wieder aufgenommene Verfahren gegen X._ ein und auferlegte ihm die Kosten der Untersuchung von Fr. 116'613.10.
Dagegen erhob X._ Beschwerde. Das Obergericht des Kantons Zug hiess diese am 21. Oktober 2015 teilweise gut. Es auferlegte X._ die Kosten des Untersuchungsverfahrens nur zu sechs Zehntel und nahm den Rest auf die Staatskasse. Für die Kosten des Beschwerdeverfahrens nahm es dieselbe Aufteilung vor.
B.
X._ beantragt mit Beschwerde in Strafsachen, das obergerichtliche Urteil sei in Bezug auf die Kostenverlegung aufzuheben und die gesamten Kosten des Verfahrens seien auf die Staatskasse zu nehmen.
C.
Das Obergericht des Kantons Zug beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei, und verweist auf die Erwägungen im angefochtenen Entscheid. Die Staatsanwaltschaft schliesst ebenfalls auf Abweisung der Beschwerde.
X._ erhielt Gelegenheit, zu den Vernehmlassungen Stellung zu nehmen.

Erwägungen:
1.
1.1. Der Beschwerdeführer bringt zusammengefasst vor, die Vorinstanz stütze sich für die Kostenauflage zu Unrecht auf Art. 5 des Zweiten Zusatzprotokolls vom 8. November 2001 zum Europäischen Übereinkommen über die Rechtshilfe in Strafsachen (nachfolgend: Zweites Zusatzprotokoll; SR 0.351.12). Diese Bestimmung regle die Kostenauferlegung zwischen den Rechtshilfe leistenden Staaten. Die Beschwerdegegnerin habe den deutschen Behörden die in der Schweiz angefallenen Kosten im Hinblick auf eine mögliche Auferlegung an eine Partei gemeldet. Die Beschwerdegegnerin habe die Auferlegung der Kosten mithin an die Oberstaatsanwaltschaft Köln delegiert. Diese habe davon abgesehen, dem Beschwerdeführer Kosten aufzuerlegen. Daran sei die Beschwerdegegnerin gebunden. Auf diesen Umstand gehe die Vorinstanz mit keinem Wort ein. Die Kostenauflage verstosse zudem gegen <ref-law> respektive <ref-law> und verletze die Unschuldsvermutung. Die Oberstaatsanwaltschaft Köln habe das Ermittlungsverfahren gegen den Beschwerdeführer mangels hinreichenden Tatverdachts eingestellt, da nicht mit hinreichender Sicherheit nachweisbar sei, dass er zur Tatzeit strafrechtlich bedeutsame Positionen bei den angeblich in betrügerische Handlungen verstrickten Gesellschaften inne gehabt habe. Zu diesem Schluss sei die Oberstaatsanwaltschaft Köln trotz ausführlicher gegenteiliger Argumentation der Beschwerdegegnerin gekommen. Es gehe nicht an, dass die Kostenauflage nun mit diesen durch die Oberstaatsanwaltschaft Köln als nicht nachweisbar erachteten Umständen begründet werde. Die Vorinstanz stelle den Sachverhalt insoweit willkürlich fest. Sie kehre die Beweislast um, wenn sie erwäge, der Beschwerdeführer mache nur pauschal und nicht in substanziierter Weise geltend, für gewisse Vorgänge in den fraglichen Gesellschaften nicht verantwortlich gewesen zu sein. Es sei zudem unzulässig, wenn sich die Vorinstanz für ihre Argumentation auf Urteile gegen eine im gleichen Zusammenhang durch die schweizerischen Strafbehörden beurteilte Person stütze. Nach der Abtretung seines Verfahrens an die deutschen Strafbehörden sei er in die Verfahren in der Schweiz nicht mehr involviert gewesen, weshalb nicht darauf abgestellt werden könne.
1.2. Die Vorinstanz erwägt, die Tatsache, dass dem Beschwerdeführer die Kosten des in Deutschland gegen ihn geführten Verfahrens nicht auferlegt worden seien, hindere nicht daran, ihm die Kosten des von der Beschwerdegegnerin durchgeführten Untersuchungsverfahrens zu überbinden, wenn die entsprechenden Voraussetzungen erfüllt seien. Unzulässig wäre es gemäss Vertrag vom 13. November 1969 zwischen der Schweizerischen Eidgenossenschaft und der Bundesrepublik Deutschland über die Ergänzung des Europäischen Übereinkommens über die Rechtshilfe in Strafsachen vom 20. April 1959 und die Erleichterung seiner Anwendung (nachfolgend: Zusatzvertrag; SR 0.351.913.61), den Beschwerdeführer trotz eines Freispruchs oder einer Einstellung im deutschen Verfahren erneut strafrechtlich zu verfolgen. Weder das Europäische Übereinkommen über die Rechtshilfe in Strafsachen vom 20. April 1959 (nachfolgend: EUeR; SR 0.351.1) noch der Zusatzvertrag gäben den Behörden des ersuchten Staates eine Handhabe, über die im ersuchenden Staat angefallenen Kosten zu entscheiden. Das Zweite Zusatzprotokoll sehe im Gegenteil vor, dass die an der Rechtshilfe beteiligten Staaten voneinander mit einigen hier nicht interessierenden Ausnahmen keine Erstattung von Kosten verlangten. Es müsse mithin jedem Staat überlassen bleiben, seine eigenen Kosten zu verlegen.
1.3. Für die Rechtshilfe zwischen der Bundesrepublik Deutschland und der Schweiz sind in erster Linie die Bestimmungen des EUeR, dem beide Staaten beigetreten sind, das Zweite Zusatzprotokoll und der zwischen ihnen abgeschlossene Zusatzvertrag massgebend. Soweit diese Staatsverträge bestimmte Fragen nicht abschliessend regeln, kommt das schweizerische Landesrecht - namentlich das Bundesgesetz über internationale Rechtshilfe in Strafsachen vom 20. März 1981 (Rechtshilfegesetz, IRSG; SR 351.1) und die dazugehörige Verordnung (IRSV; SR 351.11) - zur Anwendung (<ref-law>; Urteil 1A.63/2007 vom 28. Februar 2008 E. 1.1; vgl. auch <ref-law>).
1.4.
1.4.1. Das EUeR, das Zweite Zusatzprotokoll und der Zusatzvertrag sehen vor, dass die Rechtshilfe leistenden Staaten die in ihrem Land angefallenen Kosten grundsätzlich nicht beim jeweils anderen Staat einfordern können (vgl. Art. 20 EUeR; Art. 5 Zweites Zusatzprotokoll; Art. XII Abs. 8 Zusatzvertrag; vgl. auch ROBERT ZIMMERMANN, La coopération judiciaire internationale en matière pénale, 4. Aufl. 2014, N. 462 ff.). Ob die schweizerischen Strafbehörden die in der Schweiz angefallenen Kosten nach Abtretung des Verfahrens einer Partei auferlegen dürfen, ergibt sich aus diesen Staatsverträgen nicht ausdrücklich. Massgebend für die Beurteilung dieser Frage ist somit insbesondere das IRSG (vorne E. 1.3). Gemäss <ref-law> werden ausländische Ersuchen in der Regel unentgeltlich ausgeführt (Abs. 1). Der Bundesrat bestimmt die Voraussetzungen, unter denen die Kosten ganz oder teilweise dem ersuchenden Staat in Rechnung gestellt werden können (Abs. 2). Die Kosten für ein schweizerisches Ersuchen, die einem anderen Staat erstattet werden, gehen zu Lasten des Verfahrens, das zu dem Ersuchen Anlass gegeben hat (Abs. 3). Für die Kosten der stellvertretenden Strafverfolgung stellt <ref-law> besondere Regeln auf. Demnach werden die vom ersuchenden Staat festgesetzten Verfahrenskosten zu den Kosten des Verfahrens in der Schweiz geschlagen und eingefordert; sie werden dem ersuchenden Staat nicht erstattet (Abs. 1). Im umgekehrten Fall werden dem ersuchten Staat, wenn er die Verfolgung übernimmt, die in der Schweiz aufgelaufenen Verfahrenskosten gemeldet; ihre Erstattung wird nicht verlangt (Abs. 3).
1.4.2. Für die internationale Rechtshilfe in Strafsachen gelten sodann einige Bestimmungen, welche den Grundsatz "ne bis in idem" konkretisieren. Gemäss <ref-law> wird einem Rechtshilfeersuchen nicht entsprochen, wenn in der Schweiz oder im Tatortstaat der Richter aus materiellrechtlichen Gründen den Verfolgten freigesprochen oder das Verfahren eingestellt hat (Ziff. 1), oder auf eine Sanktion verzichtet oder einstweilen von ihr abgesehen hat (Ziff. 2). Umgekehrt bestimmt <ref-law>, dass bei Übernahme der Strafverfolgung durch einen anderen Staat die schweizerischen Behörden gegen den Verfolgten wegen derselben Tat keine weiteren Massnahmen ergreifen dürfen, wenn aufgrund des im ersuchten Staat ergangenen Entscheides die Voraussetzungen nach Art. 5 [Abs. 1] lit. a oder b IRSG erfüllt sind (<ref-ruling> E. 2.1 S. 451). Diese Bestimmungen sind gemäss <ref-law> nur anwendbar, soweit internationale Vereinbarungen nichts anderes bestimmen. Die vorliegend in erster Linie massgebenden Staatsverträge (vgl. vorne E. 1.3) enthalten keine anderslautenden Bestimmungen. Die Schweiz hat vielmehr einen entsprechenden Vorbehalt zu Art. 2 lit. a EUeR gemacht und behält sich das Recht vor, die Rechtshilfe auch dann abzulehnen, wenn wegen der dem Ersuchen zu Grunde liegenden Handlung gegen denselben Beschuldigten in der Schweiz ebenfalls ein Strafverfahren durchgeführt wird oder eine strafrechtliche Entscheidung ergangen ist, mit der diese Tat und seine Schuld materiell beurteilt worden sind (vgl. bereits Urteil 1A.107/1995 vom 21. August 1995 E. 4c). Art. XII Abs. 6 des Zusatzvertrags enthält ebenfalls eine entsprechende Regelung, wonach die Behörden des ersuchenden Staates von weiteren Verfolgungs- oder Vollstreckungsmassnahmen gegen den Beschuldigten wegen derselben Tat u.a. absehen, wenn eine Strafverfolgung eingeleitet wurde und wenn das Verfahren von einem Gericht oder einer Strafverfolgungsbehörde aus materiellrechtlichen Gründen endgültig eingestellt worden ist, insbesondere wenn die Eröffnung des Hauptverfahrens abgelehnt oder der Beschuldigte ausser Verfolgung gesetzt worden und die Frist für die Einlegung eines Rechtsmittels abgelaufen ist (lit. a), oder wenn er rechtskräftig freigesprochen worden ist (lit. b).
1.5. Vorliegend ergibt sich aus den Akten, dass der überwiegende Teil der dem Beschwerdeführer vorgeworfenen Sachverhalte nach deutschem Recht verjährt war (vgl. kantonale Akten, act. 2/1/1/69-72). Es stellt sich deshalb die Frage, ob insoweit eine "res iudicata" vorliegt, die der Wiederaufnahme des in der Schweiz zunächst sistierten Verfahrens entgegenstünde. Dies kann indes offen gelassen werden, da die Kostenauflage an den Beschwerdeführer ohnehin nicht mit dem massgebenden Bundesrecht vereinbar ist. Die Beschwerdegegnerin hat der Oberstaatsanwaltschaft Köln die in der Schweiz aufgelaufenen Kosten gemeldet, wie dies <ref-law> vorsieht. Da deren Erstattung gemäss dieser Bestimmung nicht verlangt wird, oblag der Entscheid über die Überbindung der Kosten damit der Oberstaatsanwaltschaft Köln. Diese verzichtete implizit darauf, indem sie dem Beschwerdeführer mit der Einstellungsverfügung vom 24. August 2012 keinerlei Verfahrenskosten auferlegte, was sowohl in Deutschland als auch der Schweiz dem Normalfall entspricht (vgl. § 467 Abs. 1 und 2 D-StPO sowie Art. 426 Abs. 1 und 2 StPO). Daran ist die Beschwerdegegnerin gebunden. Nach der Übertragung der Strafverfolgung an das Ausland dürfen die schweizerischen Strafverfolgungsbehörden über eine allfällige Kostenauflage nicht mehr selber befinden. Unzulässig ist es insbesondere, der verfolgten Person die schweizerischen Verfahrenskosten aufzuerlegen, wenn das Verfahren im Ausland zufolge Verjährung eingestellt wurde (LEA UNSELD, in: Basler Kommentar, Internationales Strafrecht, 2015, N. 8 zu <ref-law> sowie N. 9 zu <ref-law> mit Verweis auf TPF 2010 79 E. 2.3 S. 82 ff.). Für eine Kostenauflage an den Beschwerdeführer gestützt auf <ref-law> verbleibt demnach vorliegend kein Raum.
2.
Die Beschwerde ist gutzuheissen und das angefochtene Urteil aufzuheben. Es erübrigt sich damit, auf die weiteren Rügen des Beschwerdeführers einzugehen. Die Sache ist zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Es sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Zug hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen 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 Zug vom 21. Oktober 2015 aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zug hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zug, I. Beschwerdeabteilung, schriftlich mitgeteilt.
Lausanne, 13. Dezember 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: M. Widmer