Sachverhalt:
A.
Mit Verfügung vom 23. September 2015 aberkannte die Motorfahrzeugkontrolle des Kantons Solothurn A._, wohnhaft in Deutschland, gestützt auf <ref-law>, Art. 45 der Verordnung über die Zulassung von Personen und Fahrzeugen zum Strassenverkehr (VZV; SR 741.51) und Art. 42 des internationalen Übereinkommens vom 8. November 1968 über den Strassenverkehr (SR 0.741.10) den ausländischen Führerausweis für einen Monat wegen Überschreitens der zulässigen Höchstgeschwindigkeit auf der Autobahn um 32 km/h. Nachdem der erste Zustellversuch dieser Verfügung mit eingeschriebenem Brief an seine Wohnadresse in Deutschland erfolglos blieb, erfolgte am 17. Dezember 2015 eine zweite Zustellung per A-Post.
B.
Auf die gegen die Verfügung der Motorfahrzeugkontrolle von A._ erhobene und am 18. Januar 2016 der Post übergebene Beschwerde trat das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 16. Februar 2016 wegen Verspätung nicht ein.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. Mai 2016 gelangt A._ an das Bundesgericht und beantragt die Aufhebung des verwaltungsgerichtlichen Urteils und die Rückweisung der Sache zur materiellen Behandlung.
Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Motorfahrzeugkontrolle verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
Der angefochtene Entscheid betrifft in der Hauptsache die Aberkennung eines ausländischen Führerausweises und damit eine Angelegenheit des öffentlichen Rechts. Die Beschwerde richtet sich gegen den kantonal letztinstanzlichen (<ref-law>), verfahrensabschliessenden (<ref-law>) Nichteintretensentscheid eines oberen Gerichts (<ref-law>). Der Beschwerdeführer macht geltend, das Verwaltungsgericht habe seinen Anspruch auf materielle Überprüfung vereitelt. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Parteirechten gerügt werden, deren Missachtung auf eine formelle Rechtsverweigerung hinausläuft (<ref-ruling> E. 1.1 S. 4 f.; <ref-ruling> E. 2 S. 308). An der Beantwortung der Frage, ob die Vorinstanz zu Recht nicht auf das kantonale Rechtsmittel eingetreten ist, besteht folglich ein schutzwürdiges Interesse (<ref-law>). Ist die Beschwerde begründet, weist das Bundesgericht die Sache zur weiteren Beurteilung des Falles zurück; andernfalls hat es mit dem verwaltungsgerichtlichen Nichteintretensentscheid sein Bewenden (<ref-ruling> E. 3.2 S. 235 f.).
2.
2.1. Die Vorinstanz stützte ihren Nichteintretensentscheid auf die Annahme, die zweite, am 17. Dezember 2015 veranlasste Zustellung der Verfügung sei bis zum Ende ihrer Gerichtsferien am 2. Januar 2016 erfolgt, weshalb die am 18. Januar 2016 der Post übergebene Beschwerde nach Ablauf der massgeblichen Frist erhoben worden sei. Ausserdem habe sich der Vertreter des Beschwerdeführers trotz entsprechender Aufforderung nicht zur Rechtzeitigkeit des Rechtsmittels geäussert.
2.2. Der Beschwerdeführer erblickt darin eine willkürliche Sachverhaltsfeststellung, weil die Vorinstanz nicht abgeklärt habe, wann genau die zweite Briefsendung bei ihm eingetroffen sei, sondern sich damit begnügt habe anzunehmen, sie sei ihm während den Gerichtsferien zugegangen. Überdies sei diese per A-Post versandte Zustellung rechtswidrig, da im Bereich der Übermittlung von Administrativentscheiden über Fahrverbote ins Ausland kein internationales Übereinkommen bestehe, das die direkte postalische Zustellung erlaube. Vielmehr seien die Behörden in solchen Fällen gehalten, den Rechtshilfeweg durch die Vermittlung des zuständigen Bundesamts zu beschreiten. Der Beschwerdeführer scheint dabei - ohne die Bestimmung ausdrücklich zu nennen - auf <ref-law> abzustellen, wonach die Aberkennung eines ausländischen Führerausweises, die dem Betroffenen nicht in der Schweiz eröffnet werden kann, durch das Bundesamt für Strassen ASTRA auf dem Rechtshilfeweg eröffnen zu lassen ist.
2.3. Streitig ist, ob die Beschwerde an das Verwaltungsgericht rechtzeitig erhoben wurde. Nach § 67 des Gesetzes über den Rechtsschutz in Verwaltungssachen vom 15. November 1970 des Kantons Solothurn (Verwaltungsrechtspflegegesetz [VRG]; BGS 124.11) beträgt die Frist für die Verwaltungsgerichtsbeschwerde zehn Tage seit Eröffnung der Verfügung oder des Entscheids (Satz 1). Fristen, die nach Tagen oder anderen Zeiteinheiten bestimmt sind, beginnen an dem Tag zu laufen, der auf ihre Eröffnung oder auf das auslösende Ereignis folgt und gelten als eingehalten, wenn die Eingabe spätestens am letzten Tag der Frist bei der Behörde eingereicht oder zu deren Handen der schweizerischen Post übergeben wird (§ 9 VRG). Die Zustellung von Verfügungen gilt bei einer eingeschriebenen Postsendung, die nicht abgeholt worden ist, am siebten Tag nach dem erfolglosen Zustellversuch als erfolgt, sofern die Person mit einer Zustellung rechnen musste (<ref-law> i.V.m. § 58 Abs. 1 VRG). Das Verfahren des Entzugs des Führerausweises, und damit auch dasjenige für die Aberkennung der ausländischen Fahrerlaubnis (vgl. <ref-law>), richtet sich nach dem kantonalen Recht, was auch für die Eröffnung und Zustellung von Verfügungen gilt (Urteil 6S.233/2002 vom 11. Juli 2002 E. 1.4). Nach der Rechtsprechung überprüft das Bundesgericht diese kantonalen Zustellgrundsätze nur unter dem Gesichtswinkel der Willkür (vgl. <ref-ruling> E. 2b S. 92 mit Hinweis). Das Bundesrecht schreibt lediglich vor, dass die Entzugs- bzw. Aberkennungsverfügung schriftlich zu eröffnen und zu begründen ist (<ref-law>).
3.
3.1. Zu prüfen ist vorab, ob die unmittelbare postalische Zustellung der Aberkennungsverfügung vom 23. September 2015 an den in Deutschland lebenden Beschwerdeführer von Völkerrechts wegen an einem Eröffnungsmangel leidet. Trifft dies zu, darf dem Betroffenen daraus kein Nachteil erwachsen, was insbesondere für die Fristwahrung bei Rechtsmitteln von Bedeutung ist (<ref-ruling> E. 5.3 S. 306 mit Hinweisen). Das Bundesgericht geht bei Eröffnungsmängeln in Zusammenhang mit völkerrechtswidrigen Zustellungen von Verwaltungsverfügungen grundsätzlich davon aus, dass diese die Anfechtbarkeit des Rechtsaktes und nicht dessen Nichtigkeit im Sinne einer von Amtes wegen zu beachtenden absoluten Unwirksamkeit zur Folge haben (Urteil 2C_827/2015 vom 3. Juni 2016 E. 3.4).
3.2. Nach der Rechtsprechung stellt die Zustellung eines amtlichen Dokuments im Ausland, sei es einer Verwaltungsverfügung oder eines gerichtlichen Schriftstücks, einen staatlichen Hoheitsakt dar, der geeignet ist, die Souveränität bzw. die Gebietshoheit des betroffenen Staates zu verletzen und damit gegen Völkerrecht zu verstossen. In Ermangelung einer anders lautenden staatsvertraglichen Bestimmung oder eines anderweitigen Einverständnisses des betroffenen Staates ist die Verfügung daher auf dem diplomatischen oder konsularischen Weg zu eröffnen. Davon ausgenommen sind Mitteilungen rein informativen Inhalts, die keine Rechtswirkungen nach sich ziehen und deshalb direkt per Post zugestellt werden dürfen (<ref-ruling> E. 5.1 S. 305; <ref-ruling> E. 2.2 S. 626; <ref-ruling> E. 3a S. 50; <ref-ruling> E. 3b S. 310 f.; <ref-ruling> E. 2 S. 4; Urteil 2C_827/2015 vom 3. Juni 2016 E. 3.2; Verfügung K18/04 vom 18. Juli 2006 E. 1.2).
3.3. Dem Beschwerdeführer ist darin zuzustimmen, dass die Schweiz im Gegensatz zu Deutschland auf dem Gebiet der Verwaltungssachen die beiden einschlägigen Übereinkommen des Europarats (Europäisches Übereinkommen vom 24. November 1977 über die Zustellung von Schriftstücken in Verwaltungssachen im Ausland und Europäisches Übereinkommen vom 15. März 1978 über die Erlangung von Auskünften und Beweisen in Verwaltungssachen im Ausland) nicht ratifiziert, sondern lediglich unterschrieben hat (vgl. Erläuternder Bericht zum Entwurf für einen Bundesbeschluss über die Genehmigung von zwei Europäischen Übereinkommen in Verwaltungssachen, S. 47 ff., abrufbar unter <https://www.bj.admin.ch/bj/de/home/sicherheit/gesetzgebung/archiv/zssg.html>, zuletzt besucht am 2. November 2016). Zwar gehen auch mit der Unterzeichnung völkerrechtliche Verpflichtungen einher (vgl. Art. 18 des Wiener Übereinkommens vom 23. Mai 1969 über das Recht der Verträge; SR 0.111), doch sind diese hier nicht von Belang. Beide Staaten haben aber das Übereinkommen über den Strassenverkehr ratifiziert, das den Vertragsparteien das Recht einräumt, einem Führer, der in ihrem Hoheitsgebiet eine Zuwiderhandlung begeht, den Führerausweis abzuerkennen und dies der Behörde, welche die Fahrerlaubnis ausgestellt hat, mitzuteilen (Art. 42 Ziff. 1 lit. a und b). Mit Blick auf die Zustellung eines entsprechenden Beschlusses sieht das Übereinkommen aber lediglich vor, dass die ausländische Behörde gebeten werden soll, dem Betroffenen die Entscheidung mitzuteilen, sofern der Führerausweis nicht bis zum Ablauf der Aberkennungsfrist oder Ausreise zurückbehalten wird (Art. 42 Ziff. 1 lit. d).
3.4. Beim Warnungsentzug handelt es sich zwar um eine der Verkehrssicherheit willen angeordnete Verwaltungsmassnahme mit präventivem und erzieherischem Charakter, die nur teilweise strafähnliche Züge aufweist (<ref-ruling> E. 3.1.2 S. 224 mit Hinweisen). Dennoch verdient das Europäische Übereinkommen vom 20. April 1959 über die Rechtshilfe in Strafsachen (EUeR; SR 0.351.1) Beachtung, denn der dort verwendete Begriff der Strafsache ist grundsätzlich weit zu verstehen (vgl. Explanatory Report to the European Convention on Mutual Assistance in Criminal Matters, European Treaty Series No. 30, Kommentar zu Art. 1; AMBOS/POSCHADEL, in: Rechtshilferecht in Strafsachen, Baden-Baden 2015, S. 58 Rz. 5; PETER POPP, Grundzüge der Internationalen Rechtshilfe in Strafsachen, Basel 2001, S. 83 ff. Rz. 118; DONATSCH/HEIMGARTNER/MEYER/SIMONEK, Internationale Rechtshilfe unter Einbezug der Amtshilfe im Steuerrecht, 2. Aufl. 2015, S. 8 f.; vgl. ferner EGMR-Urteil Rivard gegen Schweiz vom 4. Oktober 2016 [Nr. 21563/12] § 24) und Rechtshilfe kann unter gewissen Voraussetzungen auch bei Zuwiderhandlungen gegen Rechtsvorschriften geleistet werden, die nach dem innerstaatlichen Recht des ersuchenden oder ersuchten Staates durch Verwaltungsbehörden geahndet werden (vgl. Explanatory Report to the Second Additional Protocol to the European Convention on Mutual Assistance in Criminal Matters, European Treaty Series No. 182, § 22, der ausdrücklich Strassenverkehrsdelikte als Beispiel aufführt).
3.5. Während das EUeR in seinem Art. 7 Abs. 1 die Übermittlung von Verfahrensurkunden und Gerichtsentscheidungen über den ersuchten Staat vorschreibt, erlaubt das Zweite Zusatzprotokoll vom 8. November 2001 zum EUeR (SR 0.351.12), dem sowohl die Schweiz als auch Deutschland angehören (vgl. Datenbank Staatsverträge, abrufbar unter <www.eda.admin.ch/vertraege>, zuletzt besucht am 2. November 2016), die unmittelbare postalische Zustellung dieser amtlichen Dokumente an den Betroffenen (Art. 16 Ziff. 1). Auch der bilaterale Vertrag vom 13. November 1969 zwischen der Schweizerischen Eidgenossenschaft und der Bundesrepublik Deutschland über die Ergänzung des EUeR und die Erleichterung seiner Anwendung (SR 0.351.913.61; nachfolgend: Zusatzvertrag zum EUeR) sieht in Art. IIIA vor, dass die zuständigen Stellen eines Vertragsstaates im Rahmen der Verfolgung von Straftaten und Ordnungswidrigkeiten, für die im anderen Vertragsstaat die Leistung von Rechtshilfe zulässig ist, gerichtliche und andere behördliche Schriftstücke unmittelbar durch die Post an Personen übersenden können, die sich im Hoheitsgebiet des anderen Vertragsstaates aufhalten.
Offen ist aber, ob der Entzug des Führerausweises bzw. die Aberkennung einer ausländischen Fahrerlaubnis unter den Geltungsbereich dieser Staatsverträge fällt. Dagegen sprechen die Erklärungen der Schweiz zum EUeR, deren Fokus auf Verfahren klassisch strafrechtlicher Angelegenheiten liegt (vgl. insb. Art. 3 des Bundesbeschlusses vom 27. September 1966, AS 1967 805). Indes geht aus dem Zusatzvertrag zum EUeR hervor, dass der Anwendungsbereich zumindest im bilateralen Verhältnis zwischen der Schweiz und Deutschland erweitert werden und sich mitunter auf Führerausweisentzüge erstrecken soll, so dass sich die Vertragsparteien auch in solchen, aus schweizerischer Sicht administrativmassnahmenrechtlichen Verfahren Rechtshilfe zu leisten haben. Dies ergibt sich einerseits aus Art. VIII Abs. 3 des Zusatzvertrags, wonach Verwaltungsbehörden, die Zuwiderhandlungen zu verfolgen oder über den Entzug des Führerausweises infolge einer Zuwiderhandlung gegen die Verkehrsvorschriften zu entscheiden haben, zur Stellung von Rechtshilfeersuchen berechtigt sind. Andererseits regelt Art. II Abs. 6, dass auf Ersuchen einer für den Entzug von Ausweisen für Führer von Motorfahrzeugen zuständigen Behörde dieser die strafgerichtlichen Erkenntnisse und Akten zur Verfügung zu stellen sind, soweit sie für die Entscheidung von Bedeutung sein können.
Ob der Führerausweisentzug bzw. die Aberkennung einer ausländischen Fahrerlaubnis in den Rechtshilfebereich fällt, kann letztlich jedoch dahin gestellt bleiben, da der Vertrag vom 27. April 1999 zwischen der Schweizerischen Eidgenossenschaft und der Bundesrepublik Deutschland über die grenzüberschreitende polizeiliche und justitielle Zusammenarbeit (schweizerisch-deutscher Polizeivertrag; SR 0.360.136.1) in Art. 12 Abs. 1 eine mit dem Wortlaut von Art. IIIA des Zusatzvertrags zum EUeR übereinstimmende Bestimmung enthält, die gewährleisten soll, dass behördliche Schriftstücke erleichtert per Post zugestellt werden können. Nach der zugehörigen Botschaft vom 24. November 1999 ist diese Bestimmung insbesondere im Bereich der Zuwiderhandlungen gegen die Vorschriften des Strassenverkehrs von Bedeutung (BBl 2000 862, S. 879 f.). Überdies erklärt auch das ASTRA gestützt auf Art. 12 Abs. 1 des schweizerisch-deutschen Polizeivertrags, dass Schriftstücke über die Aberkennung von Führerausweisen den Betroffenen direkt per Post nach Deutschland zuzustellen sind (vgl. Anhang 3 Ziff. 2.2 des Kreisschreibens vom 30. September 2013 betreffend Führerausweise von Personen mit Wohnsitz im Ausland; ferner CÉDRIC MIZEL, Droit et pratique illustrée du retrait du permis de conduire, Bern 2015, S. 709 Fn. 3484).
3.6. Aufgrund dieser vertraglichen Vereinbarung erweist es sich im Verhältnis zu Deutschland als völkerrechtlich zulässig, dass die Verfügung vom 23. September 2015 über die Aberkennung des ausländischen Führerausweises dem Beschwerdeführer unmittelbar postalisch zugesandt worden ist. Der erste Zustellversuch erfolgte gemäss der in den Akten liegenden Sendungsverfolgung der schweizerischen Post am 9. Dezember 2015, bevor der eingeschriebene Brief mit dem Vermerk "nicht abgeholt" am 16. Dezember 2015 retourniert wurde. Wird die Sendung nicht innert der Frist von sieben Tagen abgeholt, so gilt nach der vorerwähnten Zustellfiktion, deren Anwendbarkeit nicht in Abrede gestellt wird, dass sie am letzten Tag dieser Frist zugestellt wurde. Soweit der Beschwerdeführer vorbringt, er habe als einer, der mit dem zweigeteilten schweizerischen System bei Widerhandlungen gegen die Verkehrsvorschriften nicht vertraut sei, nicht mit einer Verfügung einer anderen als der Strafverfolgungsbehörde rechnen müssen, vermag er nicht durchzudringen. Vielmehr kann auch nach deutschem Recht eine Verwaltungsbehörde gegenüber dem fehlbaren Lenker ein bussgeldrechtliches Fahrverbot für die Dauer von einem Monat bis zu drei Monaten anordnen, wenn gegen diesen wegen einer Ordnungswidrigkeit, die er unter grober oder beharrlicher Verletzung seiner Pflichten begangen hat, eine Geldbusse festgesetzt wird (§ 25 Abs. 1 des Strassenverkehrsgesetzes [StVG] in der Fassung der Bekanntmachung vom 5. März 2003; BGBl. I S. 310, 919). Zudem entzieht die Fahrerlaubnisbehörde dem Betroffenen in einem Verwaltungsverfahren den Ausweis, wenn er sich zum Führen von Kraftfahrzeugen als ungeeignet oder nicht befähigt erweist (§ 3 Abs. 1 StVG; vgl. JANKER/ALBRECHT, Fahrverbot und Fahrerlaubnisentziehung in Deutschland nach Verkehrsverstössen im Ausland, in: René Schaffhauser (Hrsg.), Jahrbuch zum Strassenverkehrsrecht 2008, St. Gallen 2008, S. 155 ff.; PETER KÖNIG, in: Kommentar Strassenverkehrsrecht, 43. Aufl. 2015, Rz. 12 zu § 25 StVG; PETER DAUER, in: Kommentar Strassenverkehrsrecht, 43. Aufl. 2015, Rz. 13 zu § 3 StVG). Aus den Akten ergibt sich ferner, dass dem Beschwerdeführer am 23. Juli 2015 die Eröffnung des Administrativverfahrens zur Aberkennung des ausländischen Führerausweises mit eingeschriebenem Brief mitgeteilt worden war. Dessen Empfang bestreitet er nicht, weshalb er damit rechnen musste, dass die Motorfahrzeugkontrolle über die Aberkennung befinden und ihm den Entscheid zustellen wird (vgl. Urteil 1C_171/2011 vom 26. Mai 2011 E. 2.2). Somit ist es nicht unhaltbar zu fingieren, dass er die Verfügung vom 23. September 2015 ordnungsgemäss erhalten hat, weshalb die dagegen erhobene Beschwerde an das Verwaltungsgericht, die unbestrittenermassen erst am 18. Januar 2016 der Post übergeben wurde, nach Ablauf der zehntägigen Frist (unter Berücksichtigung der Gerichtsferien vom 17. Dezember 2015 bis 2. Januar 2016) erhoben wurde.
Im Übrigen trägt der Beschwerdeführer nach der Rechtsprechung die Beweislast für die Einhaltung der Beschwerdefrist (<ref-ruling> E. 7b S. 139 f.; <ref-ruling> E. 1b S. 61 f.; Urteil 2C_99/2015 vom 2. Juni 2015 E. 4.7), weshalb er sich vorliegend nicht damit begnügen konnte, die Sachverhaltsfeststellung der Vorinstanz als willkürlich zu rügen, wenn diese annahm, die zweite, am 17. Dezember 2015 veranlasste Zustellung sei ihm während den Gerichtsferien zugegangen. Vielmehr hätte er darlegen müssen, wann die Postsendung tatsächlich bei ihm eingegangen ist, um die Folgen der Beweislosigkeit abzuwenden.
4.
Nach dem Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen. Bei diesem Verfahrensausgang trägt der Beschwerdeführer die Gerichtskosten (<ref-law>) und er hat keinen Anspruch auf Parteikostenersatz (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Es wird keine Parteientschädigung zugesprochen.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Bau- und Justizdepartement und dem Verwaltungsgericht des Kantons Solothurn, Präsidentin, schriftlich mitgeteilt.
Lausanne, 15. November 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Pedretti