Sachverhalt:
A.
A.a. Die B._ AG leitete am 15. März 2017 beim Betreibungsamt Oberland, Dienststelle Obersimmental-Saanen (neu: Dienstelle Oberland West) die Betreibung auf Grundpfandverwertung gegen A._ (Alleineigentümer des Grundpfandes Grundstück C._strasse xxx in yyyy U._) für Fr. 8'696'750.-- nebst Zins ein. Das Betreibungsamt erliess am 20. März 2017 in der Betreibung Nr. zzz den Zahlungsbefehl.
A.b. Der Zahlungsbefehl konnte dem Betriebenen an der Adresse C._strasse xxx in yyyy U._ nicht zugestellt werden. Die beigezogene Gemeindepolizei U._ hat nach mehrfachen erfolglosen Zustellversuchen und anschliessender Kontaktaufnahme mit dem Rechtsvertreter des Betriebenen in ihrem Bericht vom 16. Mai 2017 festgestellt, dass der Betriebene seinen offiziellen Wohnsitz in New York hat und in absehbarer Zeit nicht in die Schweiz reisen wird. Auch das Betreibungsamt hat in der Folge mit dem Rechtsvertreter von A._ Kontakt aufgenommen und sich die Wohnadresse sowie die Erreichbarkeit seines Mandanten in New York bestätigen lassen. Ausserdem hat das Betreibungsamt den Rechtsvertreter angefragt, ob er für seinen Mandanten Betreibungsurkunden entgegennehme, was dieser unter Hinweis auf seine fehlende Vollmacht verneint hat.
A.c. Daraufhin veranlasste das Betreibungsamt am 8. Juni 2017 die rechtshilfeweise Zustellung des Zahlungsbefehls an der bereits im Betreibungsbegehren aufgeführten Wohnadresse des Betriebenen in New York. Das Rechtshilfeersuchen blieb indes erfolglos; beim Zustellversuch vom 4. Juli 2017 konnte der Betriebene dort nicht angetroffen werden. Am xx.xx.2017 erfolgte die Publikation des Zahlungsbefehls im Schweizerischen Handelsamtsblatt und im Amtsblatt des Kantons Bern.
B.
B.a. A._ gelangte am 13. Oktober 2017 an das Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen und verlangte die Aufhebung der öffentlichen Bekanntmachung des Zahlungsbefehls. Zudem ersuchte er um Wiederherstellung der Rechtsvorschlagsfrist für den Fall, dass die öffentliche Bekanntmachung als gültig erachtet werden sollte.
B.b. Am 1. Februar 2018 wies die Aufsichtsbehörde die Beschwerde ab, soweit sie darauf eintrat (Dispositiv-Ziffer 1) und trat auf das Wiederherstellungsgesuch nicht ein (Dispositiv-Ziffer 2); sie erhob keine Kosten (Dispositiv-Ziffer 3).
C.
Mit Beschwerde in Zivilsachen vom 15. Februar 2018 beantragt A._ (nachfolgend Beschwerdeführer) die Aufhebung des angefochtenen Entscheids sowie der öffentlichen Bekanntmachung des Zahlungsbefehls. Eventuell beantragt er, die Sache zu neuer Beurteilung an die Aufsichtsbehörde zurückzuweisen. Ausserdem ersucht er um aufschiebende Wirkung.
Nachdem die B._ AG (nachfolgend Beschwerdegegnerin) mit Eingabe vom 1. März 2018 erklärt hat, sich dem Gesuch um aufschiebende Wirkung nicht zu widersetzen, wurde der Beschwerde mit Verfügung der Instuktionsrichterin vom 7. März 2018 die aufschiebende Wirkung zuerkannt.
Die Aufsichtsbehörde und das Betreibungsamt haben auf eine Stellungnahme zur Beschwerde verzichtet. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten ist; eventuell sei die Sache zu neuer Beurteilung an die Aufsichtsbehörde zurückzuweisen.
Der Beschwerdeführer hat eine Replik eingereicht.

Erwägungen:
1.
1.1. Angefochten ist der Entscheid des Obergerichts des Kantons Bern, das als Aufsichtsbehörde über die Gültigkeit der öffentlichen Zustellung des Zahlungsbefehls befunden hat. Entscheide kantonaler Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen unterliegen unabhängig eines Streitwertes der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 2 lit. c BGG). Die Beschwerde gegen den kantonal letztinstanzlichen Entscheid ist fristgemäss erhoben worden (Art. 75 Abs. 1, Art. 100 Abs. 2 lit. a BGG). Der Beschwerdeführer hat ein schutzwürdiges Interesse an der Aufhebung oder Abänderung des angefochtenen Entscheids (<ref-law>). Die Beschwerde in Zivilsachen ist grundsätzlich zulässig.
1.2. Mit vorliegender Beschwerde kann namentlich die Verletzung von Bundesrecht und Völkerrecht gerügt werden (<ref-law>). In der Beschwerde ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Die Verletzung verfassungmässiger Rechte ist ebenfalls zu begründen, wobei hier das Rügeprinzip gilt (<ref-ruling> E. 1.2.2).
2.
Anlass zur Beschwerde geben die Voraussetzungen von <ref-law> für die Zustellung eines Zahlungsbefehls durch öffentliche Bekanntmachung.
2.1. Wohnt der Schuldner im Ausland, so erfolgt die Zustellung nach <ref-law> durch die Vermittlung der dortigen Behörden oder, soweit völkerrechtliche Verträge dies vorsehen oder wenn der Empfängerstaat zustimmt, durch die Post. Besteht ein Staatsvertrag, hat sich das Betreibungsamt an dessen Bestimmungen zu halten (<ref-ruling> E. 4.2; Urteil 5A_293/2013 vom 21. August 2013 E. 2.1). Nach <ref-law> wird die Zustellung durch öffentliche Bekanntmachung ersetzt, wenn der Schuldner im Ausland wohnt und die Zustellung nach Absatz 3 nicht innert angemessener Frist möglich ist.
2.2. Vorliegend hat das Betreibungsamt versucht, dem Betriebenen den Zahlungsbefehl an seiner Wohnadresse in New York zustellen zu lassen, wobei es zu Recht nach dem Haager Übereinkommen über die Zustellung gerichtlicher und aussergerichtlicher Schriftstücke im Ausland in Zivil- oder Handelssachen vom 15. November 1965 (HZÜ; SR 0.274.131) vorgegangen ist, welchem sowohl die USA als auch die Schweiz beigetreten sind. Als gerichtliche oder aussergerichtliche Urkunden in Zivil- oder Handelssachen im Sinne von Art. 1 HZÜ sind auch die Betreibungsurkunden anzusehen, sofern sie sich - wie hier - auf zivilrechtliche Forderungen beziehen (<ref-ruling> E. 4.2; Urteil 5A_17/2018 vom 4. Juli 2018 E. 3.2.2).
Gemäss Art. 5 Abs. 1 HZÜ wird die Zustellung des Schriftstücks von der Zentralen Behörde des ersuchten Staates bewirkt oder veranlasst, und zwar entweder in einer der Formen, die das Recht des ersuchten Staates für die Zustellung der in seinem Hoheitsgebiet ausgestellten Schriftstücke an dort befindliche Personen vorschreibt (Abs. 1 lit. a) oder in einer besonderen, von der ersuchenden Stelle gewünschten Form, es sei denn, diese Form sei mit dem Recht des ersuchten Staates unvereinbar (Abs. 1 lit. b). Von dem Fall des Absatzes 1 lit. b abgesehen, darf die Zustellung stets durch einfache Übergabe des Schriftstücks an den Empfänger bewirkt werden, wenn er zur Annahme bereit ist (Art. 5 Abs. 2 HZÜ). Die Zentrale Behörde des ersuchten Staates oder jede von diesem hierzu bestimmte Behörde stellt nach erfolgter oder versuchter Zustellung zuhanden der ersuchenden Stelle ein Zustellungszeugnis aus, welches Angaben über die Erledigung des Ersuchens zu enthalten hat; in ihm sind Form, Ort und Zeit der Erledigung sowie die Person anzugeben, der das Schriftstück übergeben worden ist. Gegebenenfalls sind die Umstände aufzuführen, welche die Erledigung verhindert haben (Art. 6 Abs. 1 und 2 HZÜ). Zu Recht hat die Vorinstanz angenommen, dass sich die Folgen einer fehlgeschlagenen Zustellung nicht nach dem HZÜ richten (Practical Handbook on the Operation of the Service Convention, Hague Conference on Private International Law [Hrsg.], 4. Aufl. 2016, S. 54 Rz. 165).
2.3. Die Vorinstanz hat die Ediktalzustellung gestützt auf <ref-law> als zulässig erachtet und diese Bestimmung dabei unter Hinweis auf eine Lehrmeinung (PAUL ANGST, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 23 zu <ref-law>) dahingehend ausgelegt, dass eine öffentliche Bekanntmachung auch dann erfolgen kann, wenn die Zustellung auf diplomatischem Weg versucht wurde, aber ergebnislos verlaufen ist, und die entsprechenden Unterlagen zurückgekommen sind. In tatsächlicher Hinsicht hat sie auf das Zustellungszeugnis gemäss Art. 6 HZÜ des offiziellen Zustelldiensts des Justizministeriums der Vereinigten Staaten "ABC Legal" (nachfolgend US-Zustelldienst) abgestellt. Daraus geht hervor, dass eine Zustellung gemäss Art. 5 Abs. 1 lit. a HZÜ an der Wohnadresse des Beschwerdeführers in New York versucht wurde, er aber dort nicht persönlich angetroffen wurde und die Zustellung deshalb nicht vorgenommen werden konnte.
2.4. Der Beschwerdeführer macht zusammengefasst geltend, die Vorinstanz hätte nach in jedem Fall erforderlicher Würdigung der konkreten Umstände zum Schluss kommen müssen, dass die Voraussetzungen für eine Zustellung des Zahlungsbefehls durch öffentliche Bekanntmachung nicht gegeben waren. Da die Zustellung des Zahlungsbefehls durch öffentliche Bekanntmachung nur als letztes Mittel erfolgen dürfe, hätte das Betreibungsamt zumindest noch einen weiteren Zustellversuch an seiner Wohnadresse in New York in Auftrag geben müssen. Dass eine Zustellung noch innert angemessener Frist möglich gewesen wäre, zeige auch die problemlose rechtshilfeweise Zustellung der Verfügung der Vorinstanz vom 16. Oktober 2017 am 15. November 2017, mit welcher ihn die Vorinstanz aufgefordert habe, für das betreibungsrechtliche Beschwerdeverfahren ein Zustellungsdomizil in der Schweiz zu bezeichnen.
2.5. Die Beschwerde hat Erfolg.
2.5.1. Der Gesetzgeber hat die öffentliche Publikation in <ref-law> - wie erwähnt - an die Voraussetzung geknüpft, dass die Zustellung an den im Ausland wohnhaften Schuldner nicht innert "angemessener Frist" möglich ist. Dem Betreibungsamt kommt bei der Bestimmung der im konkreten Fall angemessenen Zustellfrist damit ein Ermessen zu (PENON/WOHLGEMUTH, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, 4. Aufl. 2017, N. 25 zu <ref-law>; MYRIAM A. GEHRI, Die Ediktalzustellung von Betreibungsurkunden bei Schuldnern im Ausland, in: Schweizerisches und internationales Zwangsvollstreckungsrecht, Festschrift für Karl Spühler, 2005, S. 95 und 97; JEANNERET/LEMBO, in: Commentaire romand, Poursuite et faillite, 2005, N. 22 zu <ref-law>). Es hat dabei zu berücksichtigen, dass die Ediktalzustellung die Ausnahme bilden muss (<ref-ruling> E. 4). Entgegen der Auffassung der Vorinstanz dürfen die Voraussetzungen der Ediktalzustellung deshalb nicht generell dann als erfüllt betrachtet werden, wenn ein (vorliegend auf Art. 2 ff. HZÜ gestütztes) Zustellersuchen im ersten Anlauf keinen Erfolg hatte. Ist die Zustellung im Ausland auf Schwierigkeiten gestossen, sind vielmehr stets die konkreten Umstände des Einzelfalls zu berücksichtigen, so insbesondere die Anzahl der im ersuchten Staat vorgenommenen Zustellversuche, die Gründe des Scheiterns der Zustellung und der Zeitrahmen.
2.5.2. Vorliegend hätte die Vorinstanz - wie der Beschwerdeführer zu Recht vorbringt - in Betracht ziehen müssen, dass gemäss dem Zustellungszeugnis des US-Zustelldiensts nur ein einziger Zustellversuch (nämlich am 4. Juli 2017) stattgefunden hat und ausserdem zwischen dem Rechtshilfeauftrag des Betreibungsamts vom 8. Juni 2017 und dem Eingang des Zustellungszeugnisses gemäss Art. 6 HZÜ am 8. August 2017 erst zwei Monate vergangen waren.
Nicht stichhaltig ist demgegenüber das Vorbringen der Beschwerdegegnerin, es sei mangels Vornahme einer Ersatzzustellung möglicherweise von einer Weigerung des rechtshilfeweise ersuchten Staates auszugehen, die Zustellung vorzunehmen. Die Beschwerdegegnerin macht (zu Recht) nicht geltend, dass die persönliche Übergabe nicht die bevorzugte Zustellmethode des US-Zustelldienstes darstelle (vgl. Practical Handbook on the Operation of the Service Convention, Hague Conference on Private International Law [Hrsg.], 4. Aufl. 2016, S. 54 Rz. 164) und das Betreibungsamt hat vorliegend nicht von der Möglichkeit Gebrauch gemacht, gemäss Art. 5 Abs. 1 lit. b HZÜ neben der vorrangigen persönlichen Übergabe eine Ersatzzustellung an eine zur Haushaltung gehörende erwachsene Person oder einen Angestellten zu beantragen (wobei unklar geblieben ist, ob beim Zustellversuch vom 4. Juli 2017 eine zu diesem Personenkreis gehörende Person überhaupt angetroffen wurde). Ausserdem hat der US-Zustelldienst das Betreibungsamt im dem Zustellungszeugnis beigelegten "Investigation Report" (in welchem die im Rechtshilfegesuch angegebene Wohnadresse des Betriebenen als korrekt erachtet wurde) eingeladen, eine erneute Zustellung in Auftrag zu geben. Zuletzt ist auch nicht einzusehen, weshalb es für die Zulässigkeit der Ediktalzustellung sprechen soll, dass das Betreibungsamt zuvor über mehrere Monate erfolglos versucht hat, dem in New York wohnhaften Beschwerdeführer den Zahlungsbefehl am Betreibungsort in U._ zuzustellen. Dies zu versuchen war zwar nicht verboten (vgl. ANGST, a.a.O., N. 7 zu <ref-law>), hat bei der Anwendung von <ref-law> jedoch ausser Betracht zu bleiben.
2.5.3. Nach dem Gesagten hält die vorinstanzliche Auslegung von <ref-law> vor Bundesrecht nicht stand, was im konkreten Fall auch zu einem falschen Ergebnis geführt hat. Die Vorinstanz ist somit zu Unrecht zur Auffassung gelangt, das Betreibungsamt habe die Zustellung des Zahlungsbefehls gestützt auf <ref-law> durch öffentliche Bekanntmachung vornehmen dürfen.
3.
Offengelassen hat die Vorinstanz, ob sich der Beschwerdeführer im Sinne von <ref-law> beharrlich der Zustellung entzogen hat und die Ediktalzustellung allenfalls aus diesem Grund als zulässig zu betrachten ist. Eine Rückweisung an die Vorinstanz ist indes nicht erforderlich, weil die Verfahrensbeteiligten vor Bundesgericht dazu Stellung genommen haben und sich die Sache aufgrund der vorinstanzlichen Sachverhaltsfeststellungen und der Aktenlage als spruchreif erweist.
Nachdem sich der Beschwerdeführer vorliegend gemäss dem Bericht der Gemeindepolizei U._ in New York aufgehalten hat, kann ihm nicht angelastet werden, dass ihm der Zahlungsbefehl am schweizerischen Betreibungsort nicht zugestellt werden konnte (vgl. ANGST, a.a.O., N. 22 zu <ref-law>). Auch war der Beschwerdeführer nicht verpflichtet, seinem Rechtsvertreter eine Vollmacht (auch) zur Entgegennahme von Betreibungsurkunden einzuräumen (BGE 69 III 82; Urteil 7B.86/2006 vom 8. Februar 2007 E. 2.1). Dass der Beschwerdeführer bei dem einmaligen Zustellversuch in New York nicht persönlich angetroffen werden konnte, erlaubt schliesslich ebenfalls noch nicht den Schluss, dass er sich der Zustellung absichtlich entzogen hat.
4.
Nicht abschliessend beantwortet hat die Vorinstanz schliesslich die Frage, ob die bei ihr erhobene Beschwerde rechtzeitig erhoben worden ist. Die Frage ist zu bejahen: Die Frist zur Anfechtung des Zahlungsbefehls wegen unzulässiger öffentlicher Bekanntmachung läuft nicht, bevor der Schuldner von der öffentlichen Bekanntmachung Kenntnis erlangt hat (<ref-ruling> E. 3.1; 64 III 40 E. 1). Vorliegend hat der Beschwerdeführer geltend gemacht, am 12. Oktober 2017 durch seinen Rechtsvertreter von der öffentlichen Bekanntmachung des Zahlungsbefehls erfahren zu haben. Diese Darstellung wird durch das aktenkundige Schreiben des Anwalts der Beschwerdegegnerin an den Rechtsvertreter des Beschwerdeführers vom 11. Oktober 2017 gestützt, in welchem ersterer auf die Publikation des Zahlungsbefehls im Schweizerischen Handelsamtsblatt und im Amtsblatt des Kantons Bern sowie das ungenutzte Verstreichenlassen der Rechtsvorschlagsfrist aufmerksam gemacht hat. Da sich das Vorbringen der Beschwerdegegnerin, der Beschwerdeführer habe schon vorher von der Publikation im Amtsblatt tatsächlich Kenntnis genommen, demgegenüber letztlich auf eine unsubstanziierte Behauptung beschränkt, ist auf die schlüssige Schilderung des Beschwerdeführers abzustellen und davon auszugehen, dass die Vorinstanz die kantonale Beschwerde zu Recht materiell behandelt hat.
5.
Aus den dargelegten Gründen ist die Beschwerde gutzuheissen. Da sich die öffentliche Bekanntmachung als ungültig erweist, gilt der Zahlungsbefehl nicht als zugestellt. Das Betreibungsamt hat demnach eine neue Zustellung des Zahlungsbefehls vorzunehmen. Bei diesem Ausgang des Verfahrens wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1, Art. 68 Abs. 2 BGG). Eine Rückweisung der Sache an die Aufsichtsbehörde zur Neuregelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens (Art. 67 und Art. 68 Abs. 5 BGG) erübrigt sich, da das Verfahren vor der kantonalen Aufsichtsbehörde kostenlos war (<ref-law>) und keine Parteientschädigung zugesprochen werden durfte (Art. 62 Abs. 2 der Gebührenverordnung zum Bundesgesetz über Schuldbetreibung und Konkurs, GebV SchKG, SR 281.35).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Obergerichts des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, vom 1. Februar 2018 wird aufgehoben. Die öffentliche Zustellung des Zahlungsbefehls in der Betreibung Nr. zzz des Betreibungsamts Oberland vom xx.xx.2017 wird als ungültig aufgehoben.
2.
Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Betreibungsamt Oberland, Dienststelle Oberland West, und dem Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, schriftlich mitgeteilt.
Lausanne, 20. November 2018
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Buss