Sachverhalt:
A.
Die A._ GmbH mit Sitz in Deutschland liess die B._ AG in V._ über Fr. 1'588'890.65 betreiben. Unter anderem wurde angemerkt, die Betreibung diene der Verjährungsunterbrechung. Der Zahlungsbefehl war wie folgt adressiert: "B._ AG, C._, VR-Präsident" nebst der im Handelsregister eingetragenen Adresse. Er wurde am 16. April 2015 am Postschalter an D._ zugestellt. Am 3. Februar 2016 wurde die Konkursandrohung ebenfalls an D._ zugestellt. Nach dem Handelsregister ist dieser nicht zeichnungsberechtigt.
B.
Am 15. Februar 2016 liess die B._ AG Beschwerde an die Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn erheben. Der Hauptantrag lautete, es sei festzustellen, dass sowohl die Zustellung des Zahlungsbefehls als auch die Konkursandrohung vom 2. Februar 2016 nichtig seien. Eventuell seien der Zahlungsbefehl und die Konkursandrohung aufzuheben. Das Amt sei anzuweisen, einen neuen Zahlungsbefehl auszustellen. Dem weiteren Begehren, es sei der Beschwerde die aufschiebende Wirkung zu erteilen, wurde entsprochen. Mit Urteil vom 17. Mai 2016 hiess die Aufsichtsbehörde die Beschwerde gut und stellte fest, dass die Betreibung Nr. xxx des Betreibungsamts U._ nichtig ist (Dispositiv-Ziffer 1).
C.
Mit Beschwerde in Zivilsachen vom 30. Mai 2016 gelangt die A._ GmbH an das Bundesgericht. Die Beschwerdeführerin beantragt die Aufhebung des Entscheids der Aufsichtsbehörde sowie die Feststellung, dass der Zahlungsbefehl vom 23. März 2015 wie auch die Konkursandrohung vom 2. Februar 2016 in der Betreibung Nr. xxx des Betreibungsamts U._ gültig zugestellt worden sind bzw. dass die Betreibung gültig ist.
Das Betreibungsamt hat auf eine Vernehmlassung verzichtet. Die Aufsichtsbehörde und die Betriebene als Beschwerdegegnerin schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten ist.

Erwägungen:
1.
Angefochten ist ein Entscheid der kantonalen Aufsichtsbehörde, mit welchem die Zustellung des Zahlungsbefehls beurteilt worden ist. Entscheide kantonaler Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen unterliegen der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist - unter Vorbehalt zulässiger und hinlänglich begründeter Rügen (siehe E. 2 hiernach) - auf die Beschwerde einzutreten.
2.
2.1. Mit vorliegender Beschwerde kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>).
Die Beschwerde ist hinreichend zu begründen, ansonsten darauf nicht eingetreten werden kann (<ref-ruling> E. 2 S. 116; <ref-ruling> E. 2.1 S. 245 f.). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist dabei, dass auf die Begründung des angefochtenen Entscheids eingegangen und im Einzelnen aufgezeigt wird, worin eine vom Bundesgericht überprüfbare Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerde an das Bundesgericht nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 116, 86 E. 2 S. 89).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5 S. 401). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
3.
Anlass zur vorliegenden Beschwerde gibt die Zustellung des Zahlungsbefehls an eine juristische Person.
3.1. Richtet sich eine Betreibung gegen eine juristische Person, so erfolgt die Zustellung der Betreibungsurkunden an den Vertreter derselben (<ref-law>). Als solcher gilt für eine Aktiengesellschaft jedes Mitglied der Verwaltung sowie jeder Direktor oder Prokurist (<ref-law>). Dabei lässt es die Rechtsprechung zu, dass Betreibungsurkunden den genannten Personen auch ausserhalb des Geschäftslokals der betriebenen juristischen Person zugestellt werden, ohne dass vorgängig versucht werden muss, sie im Geschäftslokal zuzustellen (<ref-ruling> E. 2 S. 385 f.; <ref-ruling> E. 3.1 S. 113). Sodann ist möglich, einen Dritten zur Entgegennahme von Betreibungsurkunden ausdrücklich oder durch Generalvollmacht zu ermächtigen (BGE 43 III 18 E. 3 S. 22; <ref-ruling> E. 2a S. 84; Urteil 5A_750/2013 und 5A_752/2013 vom 8. April 2014 E. 4.1).
3.2. Die Vorinstanz hat erwogen, der Zahlungsbefehl sei an den Sitz der Betriebenen in V._ adressiert worden. Es sei zudem der Name des Verwaltungsratspräsidenten angegeben worden. Statt an diese Adresse sei der Zahlungsbefehl aber am Postschalter an D._ ausgehändigt worden. Dieser arbeite für die E._ AG (Tochtergesellschaft der Beschwerdegegnerin), die dieselbe Adresse habe. Er verfüge aber über keine Vollmacht, um Post für die Betriebene (Muttergesellschaft) entgegenzunehmen. Eine ordnungsgemässe Zustellung sei vorliegend gar nicht erst versucht worden. Für eine Ersatzzustellung bleibe somit kein Raum. Es sei nicht erstellt, dass je ein Vertreter der Beschwerdegegnerin den Zahlungsbefehl zu Gesicht bekommen habe, auch nicht auf Umwegen. Somit habe die Beschwerdegegnerin ihre Rechte nicht wahren und keinen Rechtsvorschlag erheben können. Ein Zahlungsbefehl und damit eine Betreibung seien nichtig, wenn der Zahlungsbefehl infolge fehlerhafter Zustellung nie in die Hände des Betriebenen gelangt sei.
3.3. Mit diesen Erwägungen setzt sich die Beschwerdeführerin kaum auseinander. Vielmehr ergänzt sie den Sachverhalt, ohne mit Aktenhinweisen darzulegen, dass sie die entsprechenden Tatsachen und tauglichen Beweismittel bereits bei der Vorinstanz eingebracht hat. Dies gilt unter anderem für die Schilderung, die Beschwerdegegnerin habe über Jahre die Zustellung von Betreibungsurkunden an D._ stillschweigend geduldet und damit als berechtigten Vertreter erscheinen lassen. Soweit sie sich diesbezüglich auf neue Beweismittel beruft, legt sie nicht dar, inwiefern die Voraussetzung für ein nachträgliches Vorbringen erfüllt sein soll (<ref-ruling> E. 3 S. 395), weshalb namentlich der Antrag auf Zeugeneinvernahme unzulässig ist. Da das Vorliegen einer Anscheinsvollmacht in tatbeständlicher Hinsicht in keiner Weise erstellt ist, ist auf die Kritik der Beschwerdeführerin an <ref-ruling>, in welchem die Figur der Anscheins- bzw. Duldungsvollmacht für die Zustellung von Betreibungsurkunden als irrelevant erachtet wurde, nicht weiter einzugehen. Soweit die Beschwerdeführerin den Verdacht äussert, dass eine ursprünglich bei der Post hinterlegte Vollmacht im Nachhinein gelöscht worden sei, stellt sie lediglich ihre eigene Darstellung derjenigen der Vorinstanz gegenüber, ohne dabei darzutun, inwiefern die vorinstanzliche Auffassung offensichtlich unrichtig sein soll. Den Anforderungen an Willkürrügen (vgl. vorne E. 2.2) genügt dies nicht, so dass nicht darauf einzutreten ist.
Vorliegend steht fest und ist unbestritten, dass es sich bei D._, der den Zahlungsbefehl entgegengenommen hat, nicht um einen Mitarbeiter - geschweige denn einen Direktor, Prokuristen oder Verwaltungsrat - der Beschwerdegegnerin handelt. Auszugehen ist sodann von der verbindlichen Feststellung der Vorinstanz, wonach die Beschwerdegegnerin D._ gegenüber dem Betreibungsamt bzw. der Post als sog. Betreibungsgehilfin nicht ausdrücklich als zur Entgegennahme von Betreibungsurkunden befugt bezeichnet und ausserdem jenem auch keine Generalvollmacht ausgestellt hatte. Dass es sich bei der Zustellung an D._ um eine zulässige Ersatzzustellung im Sinn von <ref-law> gehandelt habe, behauptet die Beschwerdeführerin zu Recht nicht. Gesetz und Rechtsprechung lassen diese nur unter der Voraussetzung zu, dass die Zustellung an einen Vertreter im Sinne von <ref-law> erfolglos versucht worden ist (<ref-ruling> E. 5a S. 13), was vorliegend nicht der Fall war. Die Annahme, die Zustellung des Zahlungsbefehls sei fehlerhaft erfolgt, erweist sich daher als bundesrechtskonform.
3.4. Die Beschwerdeführerin beanstandet die vorinstanzliche Feststellung der Nichtigkeit der Betreibung Nr. xxx in einem Eventualstandpunkt auch deshalb, weil das korrekt gestellte Betreibungsbegehren von der allfälligen nichtigen Zustellung des Zahlungsbefehls nicht tangiert werde. Letzteres ist zwar zutreffend, doch hat dies die Vorinstanz im angefochtenen Urteil gar nicht in Abrede gestellt. Erhält die Betriebene von einem fehlerhaft zugestellten Zahlungsbefehls - wie vorliegend - keine Kenntnis, so ist die Zustellung nichtig (<ref-ruling> E. 2c S. 119 mit Hinweis; KREN KOSTKIEWICZ, Schuldbetreibungs- und Konkursrecht, 2. Aufl. 2014, S. 111 Rz. 419; AMONN/WALTHER, Grundriss des Schuldbetreibungs- und Konkursrechts, 9. Aufl. 2013, § 13 Rz. 28). Damit wird auch die Konkursandrohung hinfällig. Wenn die Vorinstanz in Dispositiv-Ziffer 1 stattdessen von der Nichtigkeit der "Betreibung" spricht, lehnt sie sich dabei an eine gelegentlich ebenfalls in der bundesgerichtlichen Rechtsprechung anzutreffende Terminologie an (vgl. <ref-ruling> E. 2 S. 11; <ref-ruling> E. 1b S. 103). Hinter dieser steht die Überlegung, dass es im Falle einer ohne Wirkung bleibenden Zustellung des Zahlungsbefehls noch gar nicht zu einer hängigen Betreibung gekommen ist (<ref-law>; vgl. <ref-ruling> E. 4.1 S. 530). Diese Begriffsverwendung sollte nun freilich nicht darüber hinwegtäuschen, dass die Betreibung nicht als Ganzes unheilbar unwirksam ist. Vielmehr bleibt ein korrekt gestelltes Betreibungsbegehren von der fehlerhaften Zustellung unberührt und ist eine neue Zustellung vorzunehmen (vgl. BGE <ref-ruling> E. 2b S. 85). Insofern mag es zwar etwas präziser sein, lediglich von der Nichtigkeit der Zustellung des Zahlungsbefehls sowie der Konkursandrohung zu sprechen (in diesem Sinne auch das von der Beschwerdegegnerin im kantonalen Verfahren gestellte Begehren). Gleichwohl bleibt aber doch zu beachten, dass die Betreibung überhaupt erst mit einer wirksamen Zustellung des Zahlungsbefehls beginnt. Da vorliegend nach dem Gesagten bislang lediglich eine ohne Wirkung bleibende Zustellung an einen nicht legitimierten Empfänger stattgefunden hat, kann dem Antrag der Beschwerdeführerin auf Feststellung der Gültigkeit der Betreibung Nr. xxx nicht stattgegeben werden, wenngleich das Betreibungsbegehren an keinem Mangel leidet und daher rechtsbeständig bleibt.
4.
Die Beschwerde ist aus den genannten Gründen abzuweisen, soweit darauf einzutreten ist. Die Beschwerdeführerin wird damit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Betreibungsamt U._ und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 14. Oktober 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Buss