Sachverhalt:
A.
A.a. A._ (geboren 1981) ist tunesischer Staatsangehöriger. In den Jahren 2010 und 2011 ersuchte er erfolglos um Asyl in der Schweiz. Am 23. August 2011 reiste er erneut in die Schweiz ein und stellte ein drittes Asylgesuch. Das damalige Bundesamt für Migration (heute: Staatssekretariat für Migration) trat am 12. März 2012 auf das Gesuch nicht ein und ordnete die Wegweisung von A._ nach Italien an. Zwischenzeitlich - d.h. nach seiner erneuten Einreise im August 2011 - heiratete A._ im November 2011 die Schweizer Bürgerin B._ (geboren 1978). In der Folge bewilligte die Migrationsbehörde (heute: Migrationsamt) des Kantons Solothurn am 8. Januar 2013 das Gesuch um Familiennachzug.
A.b. Am 15. April 2013 meldete die Einwohnergemeinde E._/SO der Migrationsbehörde, dass sich die Ehegatten getrennt hätten und A._ per 1. April 2013 aus der ehelichen Wohnung nach F._/AG umgezogen sei. Nachdem die zuständige Behörde des Kantons Aargau sein Gesuch um Erteilung einer Aufenthaltsbewilligung bzw. einen Kantonswechsel abgelehnt hatte, zog A._ im September 2013 wieder nach E._/SO zu seiner Gattin. Im November 2013 fand die Kantonspolizei Solothurn im Rahmen ihrer Ermittlungen gegen A._ wegen Betäubungsmitteldelikten am gemeinsamen Wohndomizil der Ehegatten nur B._ vor. Anlässlich ihrer Erstbefragung sagte sie insbesondere aus, A._ wohne seit Juni 2012 nicht mehr bei ihr und führe seither eine Ausländerrechtsehe mit ihr; er lebe seit Oktober 2012 bei seiner neuen Partnerin C._ in F._/AG.
Im März 2014 meldete sich A._ erneut in E._/SO ab und daraufhin in G._/SO an. Auf die schriftliche Befragung zur Trennung von seiner Ehegattin teilte er am 5. Mai 2014 im Wesentlichen mit, er habe sich definitiv von ihr getrennt. B._ bestätigte die definitive Trennung seit Oktober 2013. Am 20. August 2014 meldete sich A._ wieder in E._/SO an. Im Rahmen des ihm gewährten rechtlichen Gehörs hinsichtlich der Nichtverlängerung der Aufenthaltsbewilligung und der Wegweisung aus der Schweiz brachte er am 10. September 2014 vor, er und seine Gattin hätten sich versöhnt, führten wieder einen gemeinsamen Haushalt und hätten sich von der Sozialhilfe gelöst. Das gemeinsame Zusammenleben bestätigten beide Ehegatten am 9. Dezember 2014.
Aufgrund der unklaren Wohnsituation von A._ wurde die Kantonspolizei Solothurn beauftragt, die Wohnverhältnisse in E._/SO zu überprüfen. Diese hielt am 16. März 2015 fest, dass A._ bei fünf Kontrollen nicht persönlich habe angetroffen werden können und in der Wohnung auch keine Gegenstände gefunden worden seien, die eindeutig ihm hätten zugeordnet werden können. Im Rahmen eines persönlichen Gesprächs am 26. Januar 2016 stritt B._ ihre frühere Aussage zur Ausländerrechtsehe ab und auch A._ bestritt am 14. März 2016, eine Beziehung mit C._ geführt zu haben. Aus der Sicht des Migrationsamts konnte der Verdacht auf eine Ausländerrechtsehe zwar nicht ausgeräumt werden, jedoch ergaben sich auch keine neuen Indizien diesbezüglich.
A.c. Das Migrationsamt des Kantons Solothurn sprach am 28. April 2016 gegen A._ aufgrund seiner Straffälligkeit, der angehäuften Schulden und der bezogenen Sozialhilfe eine ausländerrechtliche Verwarnung aus. Da A._ keine Ausländerrechtsehe nachgewiesen werden konnte, verlängerte das Migrationsamt in der Folge jeweils dessen Aufenthaltsbewilligung.
Am 12. April 2018 leitete das Staatssekretariat für Migration dem Migrationsamt eine E-Mail von Frau D._ aus H._ (Italien) weiter. Diese teilt darin namentlich mit, sie habe Beweise für eine Ausländerrechtsehe zwischen B._ und A._. In der Folge liess D._ dem Migrationsamt diverse Fotos von sich und A._ zukommen.
A.d. Am 31. Juli 2019 ersuchte A._ letztmals um Verlängerung seiner Aufenthaltsbewilligung und gab an, weiter mit B._ zusammen zu leben. Gleichzeitig ersuchte er um Erteilung einer Niederlassungsbewilligung. Das Migrationsamt des Kantons Solothurn gewährte A._ am 1. Oktober 2019 das rechtliche Gehör betreffend die Nichtverlängerung seiner Aufenthaltsbewilligung, die Nichterteilung der Niederlassungsbewilligung und die Wegweisung aus der Schweiz. In ihren Stellungnahmen vom 30. Oktober 2019 bzw. 11. November 2019 bestritten sowohl B._ als auch A._ das Vorliegen einer Ausländerrechtsehe.
Im Oktober 2019 zog A._ alleine in die Gemeinde I._/SO.
B.
Am 21. Januar 2020 verfügte das Migrationsamt im Namen des Departements des Innern des Kantons Solothurn, dass A._ keine Niederlassungsbewilligung erteilt, seine Aufenthaltsbewilligung nicht verlängert und er aus der Schweiz weggewiesen werde. Die Beschwerde, die A._ daraufhin beim Verwaltungsgericht des Kantons Solothurn (im Weiteren auch: Verwaltungsgericht) erhob, blieb ohne Erfolg (vgl. Urteil vom 11. September 2020). Das Verwaltungsgericht hielt ihn an, die Schweiz innerhalb von zwei Monaten ab Rechtskraft seines Urteils zu verlassen.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 15. Oktober 2020 an das Bundesgericht beantragt A._, das Urteil des Verwaltungsgerichts vom 11. September 2020 und die Verfügung des Departements des Innern vom 21. Januar 2020 seien vollumfänglich aufzuheben und es sei das Migrationsamt anzuweisen, ihm die Niederlassungsbewilligung zu erteilen. Eventuell seien das Urteil der Vorinstanz und die Verfügung des Departements des Innern aufzuheben und es sei das Migrationsamt anzuweisen, ihm die Aufenthaltsbewilligung zu verlängern. Subeventuell seien das Urteil der Vorinstanz und die Verfügung des Departements des Innern aufzuheben und die Angelegenheit zur Neubeurteilung an das Departement des Innern zurückzuweisen.
Mit Präsidialverfügung vom 16. Oktober 2020 trat das Bundesgericht auf das Gesuch A._s um Erteilung der aufschiebenden Wirkung nicht ein, da die vom Verwaltungsgericht angeordnete Ausreisefrist erst mit der Rechtskraft des Urteils vom 11. September 2020 zu laufen beginne.
Das Verwaltungsgericht und das Migrationsamt des Kantons Solothurn beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Staatssekretariat für Migration hat sich nicht vernehmen lassen.
Erwägungen:
1.
1.1. Nach Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen ausgeschlossen, auf deren Erteilung weder das Bundes- noch das Völkerrecht einen Rechtsanspruch einräumen. Der Beschwerdeführer beantragt primär die Erteilung einer Niederlassungsbewilligung. Art. 42 Abs. 3 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer und über die Integration (AIG; SR 142.20; bis 31. Dezember 2018: AuG) räumt dem Ehegatten einer Schweizerin nach fünfjährigem, ordnungsgemässem und ununterbrochenem Aufenthalt einen entsprechenden Rechtsanspruch ein, wenn die Integrationskriterien nach Art. 58a AIG erfüllt sind. Ob die Bewilligungsvoraussetzungen gegeben sind, namentlich ob der Erlöschungsgrund nach Art. 51 Abs. 1 lit. a AIG vorliegt, bildet Gegenstand der materiellen Beurteilung und ist keine Eintretensfrage (BGE 139 I 330 E. 1.1; 135 I 1 E. 1.2 und 1.2.2; Urteil 2C_723/2020 vom 3. Dezember 2020 E. 1.1). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich einzutreten (Art. 42, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 89 Abs. 1, Art. 90, Art. 100 Abs. 1 BGG).
1.2. Soweit der Beschwerdeführer die Aufhebung der Verfügung des Departements des Innern beantragt, ist allerdings auf die Beschwerde nicht einzutreten, denn diese wurde durch das angefochtene Urteil des Verwaltungsgerichts ersetzt (Devolutiveffekt); sie gilt jedoch immerhin als inhaltlich mitangefochten (BGE 134 II 142 E. 1.4 mit Hinweis).
2.
2.1. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG), prüft jedoch unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) nur die geltend gemachten Rechtsverletzungen, sofern rechtliche Mängel nicht geradezu offensichtlich sind (BGE 142 I 135 E. 1.5). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht, d.h. es ist klar und detailliert anhand der Erwägungen des angefochtenen Urteils aufzuzeigen, inwiefern die entsprechenden Rechtsnormen verletzt worden sein sollen (Art. 106 Abs. 2 BGG; BGE 140 II 141 E. 8; 139 I 229 E. 2.2).
2.2. Hinsichtlich des materiellen Ausländerrechts ist das zum Zeitpunkt geltende Recht massgebend, als der Beschwerdeführer um Verlängerung seiner Aufenthaltsbewilligung sowie gleichzeitig um Erteilung der Niederlassungsbewilligung ersuchte (31. Juli 2019; Art. 126 Abs. 1 AIG). Vorliegend kommt deshalb das AIG gemäss Stand 1. Juni 2019 bzw. in der bis zum 30. November 2019 gültigen Fassung zur Anwendung (AS 2019 1413).
2.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Es kann die tatsächlichen Feststellungen der Vorinstanz berichtigen oder ergänzen, wenn sie offensichtlich unrichtig sind oder auf einer anderen Rechtsverletzung im Sinne von Art. 95 BGG beruhen (Art. 105 Abs. 2 BGG). Der Betroffene hat darzulegen, dass und inwiefern dies klar und eindeutig der Fall ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG). Der Beschwerdeführer erhebt in diesem Zusammenhang keine Rügen. Dem bundesgerichtlichen Urteil ist somit der Sachverhalt zugrunde zu legen, wie die Vorinstanz ihn festgestellt hat.
3.
3.1. Der Beschwerdeführer rügt zunächst eine Verletzung seines Anspruchs auf rechtliches Gehör. Im Zusammenhang mit der von der Vorinstanz angenommenen jahrelangen Täuschung über den tatsächlichen Zweck der Ehe habe diese seine Ausführungen unberücksichtigt gelassen, wonach seine Beziehung zu B._ sehr gut gewesen sei, bis seine Ehegattin im Oktober 2019 erfahren habe, dass er nähere Kontakte zu Frau D._ geführt habe. Zudem sei die Vorinstanz auch nicht auf seine Argumentation eingegangen, wonach es der Wahrheit entspräche, dass keine neuen Probleme mit dem Gesetz hinzugekommen seien. Denn seine Inhaftierung in Italien sei gestützt auf ein Vergehen im Jahr 2006 erfolgt.
3.2. Aus dem Anspruch auf rechtliches Gehör nach Art. 29 Abs. 2 BV fliesst zunächst die Pflicht der Behörden, die Vorbringen der von einem Entscheid in ihrer Rechtsstellung betroffenen Person tatsächlich zu hören, zu prüfen und in der Entscheidfindung zu berücksichtigen (BGE 136 I 229 E. 5.2; Urteil 2C_432/2016 vom 26. Januar 2018 E. 3.2.1). Als weiteren Teilgehalt umfasst der Anspruch auf rechtliches Gehör die Begründungspflicht. Letztere verlangt jedoch nicht, dass sich das Gericht mit sämtlichen vorgebrachten Sachverhaltselementen, Beweismitteln und Rügen auseinandersetzt. Vielmehr kann es sich auf die wesentlichen Überlegungen, welche zum Entscheid geführt haben, beschränken, selbst wenn diese fehlerhaft sind. Die Begründung soll dem Betroffenen ermöglichen, die Tragweite des Entscheides zu erfassen und diesen in Kenntnis der Überlegungen des Gerichts anzufechten (BGE 143 III 65 E. 5.2; 141 III 28 E. 3.2.4; 138 I 232 E. 5.1 mit Hinweisen; 133 III 439 E. 3.3; Urteil 2C_723/2020 vom 3. Dezember 2020 E. 3.1.1). Die Begründungspflicht ist nur dann verletzt, wenn das Gericht auf die für den Ausgang des Verfahrens wesentlichen Vorbringen selbst implizit nicht eingeht (BGE 133 III 235 E. 5.2).
3.3. In E. 4.5 des angefochtenen Urteils erwog die Vorinstanz namentlich, dass der Beschwerdeführer mit seinen Angaben im Gesuch vom 31. Juli 2019 um Erteilung der Niederlassungsbewilligung sowohl die aussereheliche Beziehung mit D._ wie auch die Strafuntersuchung bzw. Verhaftung in Italien verschwiegen habe. Diese falschen Angaben seien offensichtlich in der Absicht erfolgt, die Niederlassungsbewilligung zu erlangen. Demzufolge ist nicht davon auszugehen, dass die Vorinstanz die Argumentation, welche im vorinstanzlichen Verfahren vorgebracht wurde, überhaupt nicht gehört hat. Die Angaben des Beschwerdeführers zu seiner ausserehelichen Beziehung und seiner Verhaftung in Italien wurden vorinstanzlich gewürdigt, allerdings nicht in seinem Sinne. Jedenfalls war es dem Beschwerdeführer aufgrund der vorinstanzlichen Urteilsbegründung möglich, das genannte Urteil sachgerecht anzufechten. Der Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV) wurde somit nicht verletzt.
4.
4.1. Im Weiteren macht der Beschwerdeführer geltend, es bestehe keine Ausländerrechtsehe, weshalb kein Widerrufsgrund im Sinne von Art. 62 AIG vorliege. Er habe sowohl einen Anspruch auf Erteilung einer Niederlassungsbewilligung (wohl gestützt auf Art. 42 Abs. 3 AIG) als auch eventuell einen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung (wohl gestützt auf Art. 50 Abs. 1 lit. a AIG). In diesem Zusammenhang bringt der Beschwerdeführer insbesondere vor, die Vorinstanz stelle undifferenziert und insgesamt auf die Aussage von D._ ab und erblicke darin Indizien für die Annahme einer Ausländerrechtsehe, obschon der tatsächliche Nachweis für die in der Aussage enthaltenen starken Indizien fehle. Damit rügt er sinngemäss, dass die Vorinstanz den Untersuchungsgrundsatz verletzt habe.
4.2. Ob eine Ausländerrechtsehe im Sinne von Art. 51 Abs. 1 lit. a AIG und Art. 51 Abs. 2 lit. a AIG geschlossen wurde bzw. ob die Migrationsbehörde über den fehlenden Willen zur Aufnahme einer tatsächlichen, ehelichen Lebensgemeinschaft getäuscht wurde, entzieht sich in der Regel dem direkten Beweis und ist nur durch Indizien zu erstellen. Grundsätzlich muss die Migrationsbehörde die Ausländerrechtsehe nachweisen. Dass eine solche vorliegt, darf dabei nicht leichthin angenommen werden. Die Behörde muss den Sachverhalt von Amtes wegen möglichst zuverlässig abklären; indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (Art. 90 AIG). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden könnten. Das gilt insbesondere, wenn bereits gewichtige Hinweise auf eine Ausländerrechtsehe hindeuten; dann darf und muss von den Eheleuten erwartet werden, dass sie auch von sich aus Umstände vorbringen und belegen, um die in eine andere Richtung weisenden Indizien zu entkräften (Urteile 2C_613/2019 vom 14. November 2019 E. 3.6.4; 2C_782/2018 vom 21. Januar 2019 E. 3.2.1 und 3.2.4 mit zahlreichen Hinweisen; 2C_279/2017 vom 25. September 2017 E. 3.1; 2C_936/2016 vom 17. März 2017 E. 2.3). Lässt die Indizienlage keinen klaren und unzweideutigen Schluss zu, ist das Vorliegen einer Ausländerrechtsehe nicht erstellt (Urteil 2C_782/2018 vom 21. Januar 2019 E. 3.2.5).
4.3. Solche Indizien können äussere Begebenheiten sein wie die Umstände des Kennenlernens, eine kurze Dauer der Bekanntschaft, eine drohende Wegweisung, das Fehlen einer Wohngemeinschaft, ein erheblicher Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den anderen oder die Bezahlung einer Entschädigung für die Heirat. Sie können aber auch innere (psychische) Vorgänge betreffen (BGE 128 II 145 E. 2.3; Urteil 2C_723/2020 vom 3. Dezember 2020 E. 4.3.3). In beiden Fällen handelt es sich um tatsächliche Feststellungen, die das Bundesgericht nur auf offensichtliche Unrichtigkeit oder Rechtsverletzung hin überprüft (Art. 97 Abs. 1 BGG; vgl. vorstehende E. 2.3). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (BGE 128 II 145 E. 2.3; Urteile 2C_723/2020 vom 3. Dezember 2020 E. 4.3.3; 2C_613/2019 vom 14. November 2019 E. 3.6.3).
4.4. Die Überprüfung der entsprechenden Indizien kann wiederholt erfolgen. Praxisgemäss kann, wenn es um die Verlängerung einer abgelaufenen Aufenthaltsbewilligung geht, das Migrationsamt aufgrund einer Gesamtwürdigung - unter Einbezug bereits früher bekannter und zusätzlicher neuer Erkenntnisse - das Vorliegen einer Ausländerrechtsehe bejahen. Der Umstand, wonach das Migrationsamt zu einem früheren Zeitpunkt zum Schluss gekommen ist, dass die Indizien für die Annahme einer Ausländerrechtsehe nicht ausreichen, verbietet dem Migrationsamt somit nicht, auf diese Indizien zurückzugreifen (Urteile 2C_723/2020 vom 3. Dezember 2020 E. 4.3.4; 2C_1019/2016 vom 9. Mai 2017 E. 3.1; 2C_740/2015, 2C_752/2015 vom 10. Februar 2016 E. 3.3). Allerdings müssen auch in diesem Fall zusätzliche, neue Erkenntnisse vorliegen, welche das Bild einer Ausländerrechtsehe vervollständigen und bis anhin bestehende Zweifel beseitigen.
5.
Die Vorinstanz stellte mittels Indizien das Vorliegen einer Ausländerrechtsehe fest. Die geltend gemachte Verletzung des Untersuchungsgrundsatzes ist in Bezug auf diese Feststellung näher zu prüfen.
5.1. Obwohl bereits aufgrund früherer Indizien Zweifel aufgekommen waren, wurde dem Beschwerdeführer die Aufenthaltsbewilligung weiterhin verlängert, da ihm das Führen einer Ausländerrechtsehe nicht rechtsgenüglich nachgewiesen werden konnte. Die Vorinstanz ist jedoch der Auffassung, dass sich seit der letztmaligen Verlängerung der Aufenthaltsbewilligung des Beschwerdeführers am 13. September 2017 neue Indizien ergeben hätten, die auf eine Ausländerrechtsehe hindeuteten. Sie berücksichtigt hierbei die Aussage von Frau D._ sowie die von ihr beigebrachten Beweismittel. D._ trat im April 2018 mit dem Staatssekretariat für Migration bzw. dem Migrationsamt des Kantons Solothurn in Kontakt und legte insbesondere dar, dass es sich bei der Ehe des Beschwerdeführers lediglich um eine Ausländerrechtsehe handle, sie während sieben Monaten eine Beziehung mit dem Beschwerdeführer geführt habe und mit ihm vom 15. Dezember 2017 bis zu seiner Inhaftierung in Italien am 22. April 2018 verlobt gewesen sei. Überdies bezahle der Beschwerdeführer seiner Ehegattin monatlich Fr. 4'000.--, gebe ihr kleinere Mengen Kokain und handle in einer Bar in J._/SO mit "Drogen".
5.2. Verdachtsmeldungen hinsichtlich einer Ausländerrechtsehe können unter anderem von Privatpersonen ausgehen. Dabei kann es sich insbesondere um Meldungen von Nachbarn, Vermietern oder anderen gemeinsamen Bekannten der Ehegatten sowie von Familienangehörigen, Freunden oder Bekannten des nachziehenden Ehegatten handeln. Ebenso können auch Personen aus dem Umkreis des nachzuziehenden oder bereits nachgezogenen Ehegatten Verdachtsmeldungen an das Migrationsamt oder die entsprechende Auslandsvertretung erstatten. Im Gegensatz zu Behörden, die Hinweise auf einer Ausländerrechtsehe auf Grundlage gesetzlicher Vorschriften übermitteln, ist bei Privatpersonen grundsätzlich offen, aus welchen Gründen sie sich ans Migrationsamt wenden. Deshalb sollte dieses aufgrund einer privaten Verdachtsmeldung keinen Verdacht auf eine Ausländerrechtsehe annehmen, ohne die persönliche Motivationslage des Absenders zu überprüfen. Selbst wenn ein solcher Verdacht angenommen wird, muss dieser vertieft geprüft werden (vgl. SEBASTIAN KEMPE, Die Schein-ehe im ausländer- und zivilverfahrensrechtlichen Verwaltungsverfahren, Zürich 2020, Rz. 291 ff.).
5.3. Welche Motive D._ zur Kontaktaufnahme mit den Schweizer Behörden bewogen, prüfte die Vorinstanz nicht. Sie stellte insgesamt auf deren Angaben ab, zumal sie ihr "glaubwürdiger" erschienen als das - wie es die Vorinstanz nennt - "seit Jahren widersprüchliche Verhalten" des Beschwerdeführers. Das Verwaltungsgericht erblickte in D._s Aussage neue Indizien, die für das Vorliegen einer Ausländerrechtsehe sprächen. Zwar bestätigen ein Strafbefehl vom 13. Februar 2013 (Busse von Fr. 300.-- wegen Besitz von Kokain zwecks Eigenkonsum, begangen im K._ Shop in J._/SO) sowie ein Anzeigerapport der Kantonspolizei des Kantons Solothurn vom 20. März 2020 (mehrfacher Verkauf von Kokain im K._ Shop in J._/SO) D._s Angaben zu den vom Beschwerdeführer verübten Betäubungsmitteldelikten. Ihre diesbezügliche Aussage stellt indessen kein Indiz für das Vorliegen einer Ausländerrechtsehe dar; sie belegt lediglich, dass der Beschwerdeführer und D._ sich kannten und sich über persönliche Angelegenheiten austauschten. Auch die eingereichten Fotos, die auf eine gemeinsame Beziehung zwischen ihr und dem Beschwerdeführer hindeuten, lassen per se nicht auf eine Ausländerrechtsehe schliessen, zumal der Beschwerdeführer nicht bestreitet, eine "Affäre" mit D._ eingegangen zu sein. Die behauptete Verlobung des Beschwerdeführers mit D._ liess die Vorinstanz ungeprüft, obwohl eine solche weder aus der Fotodokumentation noch aus den sonstigen Akten ersichtlich ist. Überdies sind auch für D._s Aussage, wonach der Beschwerdeführer seiner Ehefrau monatlich rund Fr. 4'000.-- bezahle und ihr zudem kleinere Mengen Kokain überreiche, keine Belege ersichtlich; diesbezügliche vertiefte Abklärungen unterliess die Vorinstanz ebenfalls.
Bereits aufgrund früherer Indizien kamen Zweifel an der Absicht des Beschwerdeführers auf, eine eigentliche Lebensgemeinschaft zu führen (vgl. vorstehende E. 5.1). Da dem Beschwerdeführer gestützt darauf indessen keine Ausländerrechtsehe nachgewiesen werden konnte, hätte die Vorinstanz für die erneute Verdachtsannahme zunächst D._s Motivationslage überprüfen müssen. Im Anschluss hätte das Verwaltungsgericht diesen Verdacht auf eine Ausländerrechtsehe vertieft abklären müssen. Sie hätte nicht bloss aufgrund der "Glaubwürdigkeit" von D._s Aussage zu den Betäubungsmitteldelikten und der auf den Fotos ersichtlichen vorübergehenden gemeinsamen Beziehung ohne weitere Abklärungen (insbesondere hinsichtlich der angeblichen Verlobung und der monatlichen Bezahlung der Ehefrau) ihre gesamte Aussage als Indiz für das Vorliegen einer Ausländerrechtsehe werten dürfen. Denn alleine aufgrund der zeitlich befristeten ausserehelichen Beziehung und den gegenseitigen Kenntnissen als einziges neues Indiz kann nicht auf das Vorliegen einer Ausländerrechtsehe geschlossen werden. Stattdessen hätten gerade die angebliche Bezahlung der Ehefrau und die geltend gemachte Verlobung mit einer anderen Partnerin bzw. die dadurch manifestierte Intensität der ausserehelichen Beziehung abgeklärt werden müssen, zumal sie die einzigen Teilgehalte von D._s Aussage sind, die grundsätzlich als Indizien für eine Ausländerrechtsehe hätten herangezogen werden können. Insgesamt wären im Zusammenhang mit der Aussage von D._ vertiefte Abklärungen angezeigt gewesen, um Indizien für oder gegen die Annahme einer Ausländerrechtsehe zu gewinnen. Indem die Vorinstanz die entsprechenden Verdachtsabklärungen unterliess, hat sie den Untersuchungsgrundsatz verletzt. Die formelle Natur dieser Rechtsverletzungen hat zur Folge, dass das angefochtene Urteil ungeachtet der materiellen Begründetheit der Beschwerde aufzuheben ist (vgl. BGE 144 I 11 E. 5.3; 137 I 195 E. 2.2).
6.
6.1. Nach dem Gesagten verletzt das Urteil der Vorinstanz Bundesrecht und ist aufzuheben. Das Bundesgericht kann zwar den Sachverhalt von Amtes wegen berichtigen oder ergänzen, wenn die Sachverhaltsfeststellung der Vorinstanz offensichtlich unrichtig ist oder auf einer Rechtsverletzung beruht (Art. 105 Abs. 2 BGG). Solches rechtfertigt sich vorliegend aber nicht, da weitere Beweismassnahmen durchzuführen und zu würdigen sein werden. Die Sache ist folglich an die Vorinstanz zur ergänzenden Sachverhaltsfeststellung und Neubeurteilung im Sinne der Erwägungen zurückzuweisen.
6.2. Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind keine Gerichtskosten zu erheben (vgl. Art. 66 Abs. 4 BGG). Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (vgl. Art. 68 Abs. 1 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen. Das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 11. September 2020 wird aufgehoben. Die Sache wird zur ergänzenden Sachverhaltsfeststellung und Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Solothurn hat dem Beschwerdeführer eine Parteientschädigung von Fr. 2'500.-- zu bezahlen.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 6. April 2021
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Meyer