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.