Sachverhalt:
A.
A.a. B.A._ und A.A._ heirateten 1991 in U._, Deutschland. Sie haben zwei gemeinsame Kinder (geboren 1992 und 1993). Am 7. Mai 2003 schied das Amtsgericht Bad Neuenahr-Ahrweiler, Deutschland, die Ehe. Über die Nebenfolgen der Scheidung einigten sich B.A._ und A.A._ vergleichsweise. Hierbei verpflichtete sich A.A._, an B.A._ ab Juni 2003 monatlich Kindesunterhalt von EUR 265.-- und Ehegattenunterhalt von EUR 870.-- zu bezahlen.
A.b. Mit Klage vom 29. Dezember 2005 verlangte A.A._ die Herabsetzung des Ehegattenunterhalts. Das Amtsgericht Bad Neuenahr-Ahrweiler änderte mit Urteil vom 3. Mai 2007 den Vergleich vom 7. Mai 2003 und setzte den Unterhalt auf monatlich EUR 707.16 zwischen dem 1. Februar 2006 und dem 31. März 2007 und auf monatlich EUR 857.16 ab dem 1. April 2007 fest.
A.c. Im Jahre 2006 zog B.A._ während des in Deutschland hängigen Abänderungsprozesses mit den gemeinsamen Kindern in die Schweiz.
B.
Mit Klage vom 12. November 2013 ersuchte A.A._ das Richteramt Dorneck-Thierstein um Aufhebung des Urteils vom 3. Mai 2007 im Unterhaltspunkt und um Feststellung, dass er ab dem 14. Januar 2013 keinen Ehegattenunterhalt mehr schulde. Das Richteramt hiess die Klage am 21. Mai 2015 insoweit gut, als es A.A._ verpflichtete, vom 1. Januar 2016 bis und mit 31. Dezember 2019 einen reduzierten Unterhaltsbeitrag von monatlich EUR 557.16 zu zahlen. Im Übrigen wies es die Klage ab.
C.
Gegen dieses Urteil reichten sowohl B.A._ als auch A.A._ Berufung beim Obergericht des Kantons Solothurn ein, wobei A.A._ seine vor der Vorinstanz gestellten Anträge wiederholte. Mit Urteil vom 9. März 2016 (eröffnet am 14. März 2016) wies das Obergericht die Berufung von A.A._ ab. Dagegen hiess es die Berufung von B.A._ gut, hob die vom Richteramt verfügte Reduktion des Unterhaltsbeitrags auf und wies die Abänderungsklage von A.A._ ab.
D.
Mit Beschwerde in Zivilsachen vom 28. April 2016 gelangt A.A._ (Beschwerdeführer) an das Bundesgericht und beantragt, es seien die Urteile des Obergerichts vom 9. März 2016 und des Amtsgerichts Bad Neuenahr-Ahrweiler vom 3. Mai 2007 im Unterhaltspunkt aufzuheben. Weiter sei festzustellen, dass er ab 12. November 2013 keinen Unterhalt mehr schulde. Eventualiter sei das Verfahren an die Vorinstanz zurückzuweisen. Ausserdem verlangt A.A._, es seien sämtliche bisher angefallenen Prozesskosten B.A._ aufzuerlegen.
Mit Eingaben vom 9. und vom 22. November 2016 beantragen das Obergericht des Kantons Solothurn und B.A._ (Beschwerdegegnerin) die Abweisung der Beschwerde. Letztere ersucht ausserdem um Gewährung der unentgeltlichen Rechtspflege. Mit Stellungnahme vom 8. Dezember 2016 hält A.A._ an seinen bisherigen Anträgen fest.

Erwägungen:
1.
1.1. Die Beschwerde richtet sich gegen den Endentscheid einer letzten kantonalen Instanz, die als oberes Gericht über die Änderung der vermögensrechtlichen Folgen einer Ehescheidung und damit eine vermögensrechtliche Zivilsache entschieden hat (Art. 72 Abs. 1, Art. 75 Abs. 1 und Art. 90 BGG). Der Streitwert übersteigt Fr. 30'000.-- (Art. 74 Abs. 1 Bst. b und <ref-law>; vgl. <ref-ruling> E. 2 S. 395). Die Beschwerde in Zivilsachen ist daher grundsätzlich zulässig. Der Beschwerdeführer ist gemäss <ref-law> zur Beschwerde berechtigt und die Beschwerdefrist ist eingehalten (Art. 100 Abs. 1 und Art. 46 Abs. 1 Bst. a BGG). Auf die Beschwerde kann daher eingetreten werden.
1.2. Der Beschwerdeführer beantragt, es sei das Urteil vom 3. Mai 2007 aufzuheben und festzustellen, dass er ab dem 12. November 2013 keinen Ehegattenunterhalt mehr schulde (vorne Bst. D). Diese Begehren sind im Lichte der Begründung der Beschwerde nach Treu und Glauben auszulegen (vgl. <ref-ruling> E. 1.3 S. 317; <ref-ruling> E. 2a S. 152; Urteil 4A_219/2016 vom 12. September 2016 E. 1.3). Nach Ansicht des Beschwerdeführers entfällt ab dem 12. November 2013 der Grund für seine Unterhaltspflicht (Beschwerde, Ziff. 2 S. 4). Obgleich er ein Feststellungsbegehren stellt, ersucht er damit in Abänderung des Urteils vom 3. Mai 2007 um Aufhebung seiner Unterhaltspflicht ab dem 12. November 2013. Die Beschwerde ist entsprechend entgegen zu nehmen.
2.
2.1. Umstritten ist die Änderung des Urteils des Amtsgerichts Bad Neuenahr-Ahrweiler vom 3. Mai 2007, in dem dieses den vom Beschwerdeführer geschuldeten nachehelichen Unterhalt neu festsetzte (vorne Bst. A.b und E. 1.2). Die Vorinstanz ging von der unangefochten gebliebenen Annahme aus, dass deutsches Recht zur Anwendung gelange. Das trifft zu, weil das auf die Scheidung anwendbare Recht auch für die Abänderung des Scheidungsurteils massgebend ist (Art. 61 Abs. 2 i.V.m. Art. 64 Abs. 2 sowie Art. 49 IPRG [SR 291] und Art. 8 des Haager Übereinkommens vom 2. Oktober 1973 über das auf Unterhaltspflichten anzuwendende Recht [SR 0.211.213.01]).
2.2. Dem Bundesgericht ist es in der vorliegenden vermögensrechtlichen Angelegenheit (vgl. vorne E. 1.1) versagt, die Anwendung des ausländischen Rechts frei zu prüfen. Zulässig ist einzig die Rüge der willkürlichen Rechtsanwendung (Art. 96 Bst. b BGG im Umkehrschluss und Art. 95 Bst. a BGG i.V.m. <ref-law>; <ref-ruling> E. 4.3 S. 495; <ref-ruling> E. 3.2.3 S. 669; <ref-ruling> E. 3.1 S. 447 f.). Entgegen dem Vorbringen des Beschwerdeführers hat das Obergericht deutsches Recht angewandt und nicht, auch nicht teilweise, auf das schweizerische Recht zurückgegriffen, was nach Art. 96 Bst. a BGG mit Beschwerde gerügt werden könnte (vgl. etwa <ref-ruling> E. 3c/dd S. 496). Soweit das Obergericht auf das schweizerische Recht verwies, hat es lediglich rechtsvergleichend aufgezeigt, dass dieses keine andere Lösung vorsieht. Nicht stichhaltig ist weiter die ohnehin nur schwer verständliche Rüge, die Vorinstanz habe ein Gutachten zum Inhalt des deutschen Rechts einholen sollen. Bei diesem Recht handelt es sich um das Recht eines Nachbarstaates, welches festzustellen das Obergericht in der Lage war. Die Rechtsanwendung auf den konkreten Fall, mit welcher der Beschwerdeführer nicht einverstanden ist, ist sodann Aufgabe des Richters und nicht des Gutachters. Ein entsprechendes Gutachten erübrigte sich daher (vgl. <ref-ruling> E. 2c/bb S. 94; vgl. auch <ref-ruling> E. 3.4 S. 425).
2.3. Willkür in der Rechtsanwendung liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 4.1 S. 566; <ref-ruling> E. 3.2.5 S. 339). Willkür in der Rechtsanwendung prüft das Bundesgericht nur, wenn und soweit entsprechende Rügen erhoben und begründet werden, d.h. klar und detailliert anhand der Erwägungen des angefochtenen Urteils dargelegt wird, inwiefern das Willkürverbot verletzt sein soll (<ref-law>; <ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 1.4 S. 176).
3.
3.1. Das Obergericht ging mit der Erstinstanz davon aus, die Parteien hätten im Vergleich vom 7. Mai 2003 Unterhaltszahlungen für die Betreuung der damals zehn und elfjährigen Kinder (sog. Betreuungsunterhalt) vereinbart. Der Unterhalt sei unabhängig von Alter und Ausbildungsstand der Kinder vorgesehen worden. Dies ergebe sich daraus, dass der Unterhaltsanspruch nicht befristet worden sei, obgleich solches möglich gewesen wäre. Im ersten Abänderungsverfahren sei eine Reduktion bzw. ein Wegfall des Betreuungsaufwands der damals bereits im Teenager-Alter stehenden Kinder sodann kein Thema gewesen. Daher hätten die Parteien über den Betreuungsunterhalt hinaus (unbefristete) Unterhaltsleistungen vereinbart. Es liege nun am Beschwerdeführer, wesentliche Veränderungen nachzuweisen, die eine Änderung dieser Leistungen erlaubten. Diesen Beweis habe er nicht erbracht. Die Beschwerdegegnerin schliesst sich im Wesentlichen der Argumentation des Obergerichts an.
3.2. Nach Ansicht des Beschwerdeführers ist die Annahme unhaltbar, dass die Parteien unabänderlichen Unterhalt vereinbart hätten. Zwar enthalte weder der Vergleich vom 7. Mai 2003 noch das Urteil vom 3. Mai 2007 eine Befristung des Unterhaltsanspruchs. Eine solche sei aber auch nicht üblich gewesen, sodass hieraus nichts abgeleitet werden könne. Es sei Betreuungsunterhalt vereinbart worden, der heute mangels Betreuungsbedürftigkeit der Kinder nicht mehr geschuldet sei. Jedoch frage sich, ob Unterhaltszahlungen aus einem anderen Grund möglich seien. Für das Erlöschen des ursprünglichen Unterhaltsgrunds sei der Beschwerdeführer beweisbelastet. Der Beweis für das Bestehen eines neuen Unterhaltsgrunds obliege dagegen der Beschwerdegegnerin. Diesen Beweis habe sie nicht erbringen können. Ohnehin sei dem Beschwerdeführer der (Gegen) Beweis gelungen, dass die Beschwerdegegnerin ein bedarfsdeckendes Einkommen erwirtschafte, weshalb namentlich kein Aufstockungsunterhalt geschuldet sei. Die Vorinstanz habe in Verkennung dieser Grundsätze das massgebende deutsche Recht willkürlich angewandt.
4.
4.1. Gemäss § 238 des Gesetzes vom 17. Dezember 2008 über das Verfahren in Familiensachen und in den Angelegenheiten der freiwilligen Gerichtsbarkeit (FamFG; BGBl. I S. 2586, 2587) kann jeder Teil die Abänderung einer in der Hauptsache ergangenen Endentscheidung des Gerichts verlangen, die eine Verpflichtung zu künftig fällig werdenden wiederkehrenden Leistungen enthält. Der Antrag ist zulässig, sofern der Antragsteller Tatsachen vorträgt, aus denen sich eine wesentliche Veränderung der der Entscheidung zugrunde liegenden tatsächlichen oder rechtlichen Verhältnisse ergibt (Abs. 1). Der Antrag kann nur auf Gründe gestützt werden, die nach Schluss der Tatsachenverhandlung des vorausgehenden Verfahrens entstanden sind und deren Geltendmachung durch Einspruch nicht möglich ist oder war (Abs. 2; sog. Tatsachenpräklusion). Ein Abänderungsantrag darf daher nicht auf Gründe gestützt werden, die im früheren Verfahren bereits eingetreten oder mit Sicherheit vorauszusehen waren (BUMILLER/HARDERS/SCHWAMB, Kurzkommentar FamFG, 11. Aufl. 2015, N. 3 f. und 13 zu § 238 FamFG mit Hinweis).
4.2. Nach Ansicht des Obergerichts haben die Parteien über den Betreuungsunterhalt hinausgehende Unterhaltsleistungen vereinbart (vorne E. 3.1). Es begründete diese Annahme damit, dass die Beschwerdegegnerin durch die Kinderbetreuung einen Erwerbsunterbruch erlitten habe. Ausserdem müsse sie die sich daraus ergebenden Folgen für ihr berufliches Fortkommen tragen. Die Vorinstanz nahm damit neben dem Betreuungsunterhalt auch Erwerbslosen- oder Aufstockungsunterhalt an (so ausdrücklich die Erstinstanz; Urteil vom 21. Mai 2015, Ziff. II E. 2e S. 8 f. [Akten Richteramt DTPR.2013.567, pag. 312 ff.]). Dies scheint fraglich: Dem Vergleich vom 7. Mai 2003 lag die Annahme zugrunde, sämtliche Arbeitsbemühungen der Beschwerdegegnerin seien angesichts der Kinderbetreuung überobligatorisch und nicht anrechenbar (vgl. Schreiben des Amtsgerichts vom 19. Dezember 2002 [Beschwerdebeilage 4], S. 4). Neben der Kinderbetreuung musste diese also kein Erwerbseinkommen erzielen, was allenfalls Anlass zu Erwerbslosen- oder Aufstockungsunterhalt hätte geben können (vgl. HANS-ULRICH MAURER, in: Münchener Kommentar, Bürgerliches Gesetzbuch, Band 7, 4. Aufl. 2000 [nachfolgend: 4. Aufl.], N. 1 und 21 zu a§ 1570 BGB). Ausserdem hielt das Amtsgericht im Urteil vom 3. Mai 2007 ausdrücklich fest, es sei dem Grunde nach Betreuungsunterhalt geschuldet (Entscheidgründe, S. 4 [Beschwerdebeilage 6]). Von anderweitigen Unterhaltsleistungen war nicht die Rede. Unbesehen darum, wie es sich hiermit verhält, handelt es sich jedoch bei den vereinbarten Unterhaltszahlungen unbestritten zum grossen Teil um Betreuungsunterhalt (vorne E. 3).
4.3. In dieser Situation kann der vom Beschwerdeführer bereits vor den Vorinstanzen geltend gemachte und vor Bundesgericht unbestritten gebliebene Wegfall der Kinderbetreuung eine wesentliche Änderung der tatsächlichen Verhältnisse im Sinn von § 238 Abs. 1 FamFG sein (vgl. BUMILLER/HARDERS/SCHWAMB, a.a.O., N. 9 zu § 238 FamFG mit Hinweis auf das Urteil des OLG Schleswig vom 24. April 2007, in: FamRZ 2008 S. 64 E. II.1). Der Wegfall des Betreuungsaufwands ist aber nur zu berücksichtigen, wenn er nicht bereits dem Vergleich vom 7. Mai 2003 oder dem Urteil des Amtsgerichts vom 3. Mai 2007 zugrunde lag (vorne E. 4.1). Wie der Beschwerdeführer richtig geltend macht, ist insoweit das im Zeitpunkt des Vergleichsschlusses bzw. der Ausfällung des Urteils anwendbare Recht massgebend, mithin das vor Inkrafttreten des Gesetzes vom 21. Dezember 2007 zur Änderung des Unterhaltsrechts (BGBl. 2007 I S. 3189) am 1. Januar 2008 geltende Recht.
4.4. Gemäss a§ 1570 BGB kann ein geschiedener Ehegatte von dem anderen Unterhalt verlangen, solange und soweit von ihm wegen der Pflege oder Erziehung eines gemeinschaftlichen Kindes eine Erwerbstätigkeit nicht erwartet werden kann. Wann es dem unterhaltsberechtigten Ehegatten zumutbar ist, eine Erwerbstätigkeit aufzunehmen, richtet sich nach den Umständen des Einzelfalls. In der Praxis hat sich als Orientierungshilfe ein auf Alter und Anzahl der Kinder beruhendes Schema durchgesetzt, wobei sich je nach Sachlage Abweichungen ergeben können (sog. Altersphasenmodell; vgl. HELMUT BÜTTNER, in: Johannsen/Heinrich [Hrsg.], Eherecht, Kommentar, 4. Aufl. 2003, N. 14 ff. zu a§ 1570 BGB; HANS-ULRICH MAURER, in: Münchener Kommentar zum Bürgerlichen Gesetzbuch, Bd. 7, 5. Aufl. 2010, N. 4 ff. zu § 1570 BGB). Obgleich damit eine gewisse Schematisierung des Betreuungsunterhalts erfolgt, wird dieser in der Praxis regelmässig unbefristet zugesprochen, da zumeist kaum vorhersehbar ist, wann und in welchem Umfang die unterhaltsberechtigte Person Einkünfte erzielen kann. Anderes gilt nur dann, wenn die Begrenzung des Unterhaltsanspruchs sicher vorhersehbar ist (statt vieler Urteil des BGH vom 9. Juni 2004 E. 3, in: NJW 2004 S. 3106 ff., 3108; HELMUT BÜTTNER, a.a.O., N. 28 zu a§ 1570 BGB; HANS-ULRICH MAURER, 4. Aufl., N. 18 zu a§ 1570 BGB; OTMAR HÄBERLE, in: Soergel, Kommentar zum Bürgerlichen Gesetzbuch, 13. Aufl. 2013, N. 32 zu § 1570; HELMUT BORTH, in: Dieter Schwab [Hrsg.], Handbuch des Scheidungsrechts, 3. Aufl. 1995, S. 738 f.).
4.5. Die Vorinstanz verkennt diese Grundsätze, wenn sie darauf verweist, eine Befristung des Unterhaltsanspruchs der Beschwerdegegnerin sei auf den Zeitpunkt der Mündigkeit oder des Ausbildungsabschlusses der Kinder möglich gewesen. Diese Ereignisse treten im Leben eines jeden Kindes mit Sicherheit ein. Würde hierdurch der Wegfall des Betreuungsaufwands und die Wiederaufnahme einer Erwerbstätigkeit sicher vorhersehbar, müsste der Unterhaltsanspruch stets befristet werden. Dies ist wie ausgeführt aber gerade nicht der Fall. Die Tatsache, dass die Kinder der Parteien einmal mündig oder eine Ausbildung abschliessen werden, liess eine Befristung des Betreuungsunterhalts folglich nicht erwarten. Damit ist es nicht vertretbar, aus der fehlenden Befristung zu schliessen, die Parteien hätten den Wegfall des Betreuungsaufwands bereits im Vergleich vom 7. Mai 2003 berücksichtigt, wie die Vorinstanz dies tut. Auch andere Umstände, welche diesen Schluss zulassen würden (vgl. etwa Urteil des BGH vom 9. Juni 2004 E. 3, in: NJW 2004 S. 3106 ff., 3108), ergeben sich aus dem angefochtenen Urteil nicht. Die Vorinstanz führt sodann selbst aus, eine Reduktion bzw. ein Wegfall des Betreuungsaufwandes sei nicht Thema des späteren Abänderungsverfahrens gewesen. Damit ist auch nicht ersichtlich, weshalb dieser dem Urteil des Amtsgerichts vom 3. Mai 2007 hätte zugrunde liegen sollen. Soweit der hier interessierende Betreuungsunterhalt betreffend, sind die Ausführungen der Vorinstanz zur Befristung des Erwerbslosen- bzw. Aufstockungsunterhalts schliesslich nicht einschlägig.
4.6. Es erweist sich damit als unhaltbar, den vom Beschwerdeführer bereits vor der Vorinstanz geltend gemachten Wegfall des Betreuungsaufwands von vornherein nicht zu berücksichtigen. Vielmehr wäre das Obergericht gehalten gewesen, das Vorbringen zu prüfen und das Urteil des Amtsgerichts vom 3. Mai 2007 gegebenenfalls unter Wahrung seiner Grundlagen anzupassen (§ 238 Abs. 1, 2 und 4 FamFG). Hierbei ist der Beschwerdeführer für das Erlöschen des ursprünglichen Unterhaltsgrunds beweisbelastet. Die Beschwerdegegnerin hat demgegenüber gegebenenfalls das Bestehen eines neuen Unterhaltsgrunds darzulegen und nachzuweisen (vgl. HELMUT BORTH, in: Dieter Schwab [Hrsg.], Handbuch des Scheidungsrechts, 6. Aufl. 2010, S. 838 f. und 892; HANS-ULRICH MAURER, in: Münchener Kommentar, Bürgerliches Gesetzbuch, Band 7, 6. Aufl. 2013, N. 29 f. zu § 1573 BGB; exemplarisch zum alten Recht Urteil des BGH vom 31. Januar 1991 E. 3, in: NJW 1990 S. 2752 ff., 2753). Diesbezüglich ist das heute geltende Recht anwendbar (vgl. § 36 Nr. 1 des Gesetzes vom 30. Januar 1877 betreffend die Einführung der Zivilprozessordnung in der im Bundesgesetzblatt Teil III, Gliederungsnummer 310-2, veröffentlichten Fassung [EG ZPO] und hierzu Deutscher Bundestag, Drucksache 16/1830 vom 15. Juni 2006, Kommentar zu Art. 3 Abs. 2 S. 32 ff.).
5.
5.1. Indem das Obergericht den Beschwerdeführer nicht mit dem Vorbringen hörte, dass aufgrund des Wegfalls des Betreuungsaufwands kein Betreuungsunterhalt mehr geschuldet sei, und ihn hierzu nicht zum Beweis zuliess, hat es nach dem Ausgeführten in klarer Verletzung des anwendbaren Rechts entschieden. Der Entscheid ist nicht nur in der Begründung, sondern auch in seinem Ergebnis unhaltbar, wird der Beschwerdeführer doch verpflichtet, Unterhalt für die Betreuung der gemeinsamen Kinder zu leisten, obgleich der Betreuungsaufwand möglicherweise entfallen und dieser Umstand bei der Festsetzung des Unterhalts bisher nicht berücksichtigt worden ist. Das Obergericht ist damit in Willkür verfallen, weshalb der angefochtene Entscheid aufzuheben ist. Es ist allerdings nicht Sache des Bundesgerichts, erstmals über die sich stellenden Fragen zu entscheiden. Die Beschwerde ist daher teilweise gutzuheissen und die Sache zum erneuten Entscheid an das Richteramt zurückzuweisen, welches die entsprechenden Vorbringen des Beschwerdeführers ebenfalls nicht berücksichtigte (<ref-law>; vgl. Urteil vom 21. Mai 2015 Ziff. II E. 2 S. 5 ff. [Akten Richteramt DTZPR.2013.567 pag. 309 ff.]). Dieses wird auch neu über die in den kantonalen Verfahren bisher angefallenen Prozesskosten zu entscheiden haben. Weitergehend ist die Beschwerde abzuweisen. Auf die weiteren Rügen des Beschwerdeführers, insbesondere auf diejenige der Verletzung des Anspruchs auf rechtliches Gehörs, braucht unter diesen Umständen nicht eingegangen zu werden.
5.2. Obgleich die Beschwerde nur teilweise gutzuheissen ist, obsiegt der Beschwerdeführer in der Sache vollständig. Dementsprechend sind die Gerichtskosten der Beschwerdegegnerin aufzuerlegen (<ref-law>) und hat diese dem Beschwerdeführer die Parteikosten zu ersetzen (Art. 68 Abs. 1 und 2 BGG). Allerdings sind die Voraussetzungen für die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung gegeben. Das entsprechende Gesuch der Beschwerdegegnerin ist gutzuheissen und es ist ihr ihre Rechtsvertreterin beizugeben (Art. 64 Abs. 1 und 2 BGG). Die Gerichtskosten sind vorläufig auf die Gerichtskasse zu nehmen und die Rechtsvertreterin der Beschwerdegegnerin ist aus dieser angemessen zu entschädigen. Die Beschwerdegegnerin hat der Gerichtskasse Ersatz zu leisten, wenn sie später dazu in der Lage ist (<ref-law>). Dass der Beschwerdegegnerin die unentgeltliche Rechtspflege gewährt wird, entbindet sie nicht von ihrer Pflicht, den Beschwerdeführer zu entschädigen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Solothurn, Zivilkammer, vom 9. März 2016 wird aufgehoben und die Sache zum erneuten Entscheid an das Richteramt Dorneck-Thierstein zurückgewiesen. Weitergehend wird die Beschwerde abgewiesen.
2.
Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege wird gutgeheissen und es wird ihr Advokatin Annalisa Landi als Rechtsbeiständin beigegeben.
3.
Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdegegnerin auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Advokatin Annalisa Landi wird aus der Gerichtskasse für das bundesgerichtliche Verfahren mit Fr. 3'500.-- entschädigt.
5.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen.
6.
Dieses Urteil wird den Parteien, dem Obergericht des Kantons Solothurn, Zivilkammer, dem Richteramt Dorneck-Thierstein und dem Amtsgericht Bad Neuenahr-Ahrweiler schriftlich mitgeteilt.
Lausanne, 2. Februar 2017
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Sieber