С тех пор Великий Князь стал ездить за границу каждую осень, так как, состоя в должности Командира Лейб-Гвардии Конного полка, он мог с личного разрешения Государя отлучаться из части на более или менее продолжительное время. И всякий раз, уезжая в очередное заграничное путешествие, он брал с собой А. А. Волкова. Но из всех этих поездок А. А. Волкову наиболее запомнилась вторичная поездка в Кобург в 1894 году, где состоялась помолвка будущего Императора Николая II с принцессой Гессен-Дармштадской Алисой.

С наступлением осени того же года Великий Князь Павел Александрович вместе со своим братом Великим Князем Сергеем Александровичем стали собираться в Великобританию, поскольку у Королевы Виктории возник некий план, суть которого заключалась в женитьбе рано овдовевшего князя на одной из английских принцесс. Но когда уже все было готово к отъезду, из Ливадии пришла телеграмма о том, что Государь Император Александр III находится в тяжёлом состоянии.

В Ливадии Великий Князь Павел Александрович пробыл около недели, застав последние дни жизни своего Августейшего Брата. По просьбе умирающего туда же был вызван отец Иоанн Кронштадтский, под благословение которого подходил и А. А. Волков.

Утром 20 октября 1896 года Император Александр III почил в Бозе, и А. А. Волкову в числе прочих слуг удалось проститься с покойным Государем, ещё сидевшим на кресле в домашнем халате в том самом виде, в каком Его застала смерть.

Летние месяцы следующего, 1895, года Великий Князь Павел Александрович проводил в гостях у Королевы Виктории в её родовом замке Виндзор. В этой поездке его как всегда сопровождал верный А. А. Волков, который вместе со своим господином даже участвовал в традиционной охоте на оленей и проводимом по этому поводу празднике. Однако запланированного ранее сватовства не получилось, так как князь и принцесса, что называется, не сошлись характерами.

Весной 1896 года А. А. Волков сопровождает Великого Князя Павла Александровича и его детей в Москву, где, начиная с 6 мая, проходят торжества по случаю Священного Коронования Государя Императора Николая II Александровича.

Остановившись, как всегда, в доме своего брата Сергея, Великий Князь по личному поручению молодого Государя ежедневно встречает многочисленных иностранных гостей, прибывающих в столицу. И причём всякий раз ему приходится переодеваться в военный мундир той страны, откуда приехал тот или иной именитый гость.

День Священного Коронования А. А. Волков наблюдал воочию. А на другой день он даже смог наблюдать Торжественное шествие от Красного Крыльца Грановитой палаты к Успенскому собору и обратно, но попасть в оный ему так и не удалось из-за страшной давки.

Возвратившись в Кремлевский Дворец, он встретился там с Великим Князем Павлом Александровичем, который сообщил ему, что сейчас сюда прибудет Государь Император Николай II, которому надо будет помочь переодеться. И действительно, Государь вскоре вошёл в свои покои, и А. А. Волков смог принести Ему личные поздравления.

По окончании Коронационных Торжеств, закончившихся блестящим балом у французского посланника, Великий Князь Павел Александрович возвратился в Санкт-Петербург, а ещё через несколько дней произошло его знакомство с госпожой О. В. Пистолькорс, муж которой был его однополчанином.

О возникшей между ними связи А. А. Волков узнал во время очередной поездки за границу своего господина, когда в великокняжеский салон-вагон следовавшего в Париж поезда стала постоянно наведываться госпожа О. В. Пистолькорс, ехавшая тем же поездом в вагоне 1-го класса.

По прибытии в Париж, Великий Князь Павел Александрович и О. В. Пистолькорс жили в разных комнатах одного отеля, откуда они предпринимали совместные прогулки по городу и его пригородам.

По возвращении в Санкт-Петербург их свидания стали проходить чаще, равно как и совместные обеды, – то госпожа Пистолькорс приезжала к Великому Князю, то наоборот.

На следующий год Великий Князь Павел Александрович предпринял довольно продолжительную поездку на юг Франции для морских купаний. Но на сей раз он совершал своё путешествие в узком семейном кругу – с детьми, которых сопровождала госпожа Джунковская и детский врач С. А. Остроградский. Однако вскоре туда же прибыла и О. В. Пистолькорс. Сознавая некоторую щекотливость своего положения, Великий Князь Павел Александрович стал чувствовать себя хуже и по приезде в Санкт-Петербург заболел тяжёлой формой нервной экземы, для лечения которой был вынужден отправиться в Берлин. Но теперь уже О. В. Пистолькорс находилась при нём безотлучно, ухаживая за Великим Князем Павлом Александровичем, как за больным, и проживая вместе с ним в снятом им загородном доме.

В последующие два года А. А. Волков вместе с двумя адъютантами Великого Князя: Лихачевым и Ефимовичем – сопровождал его и мадам О. В. Пистолькорс в заграничных путешествиях. Сначала – в Берлин, а затем в Париж и Италию, где влюбленные хотели тайно обвенчаться. Но из этой затеи ничего не вышло, так как Великий Князь Павел Александрович вновь стал страдать нервным расстройством. Причём, на этот раз его нервная система оказалась поражённой настолько серьёзно, что он, со слов А. А. Волкова, «находился в опасном положении». А госпожа О. В. Пистолькорс, как и прежде, ухаживала за ним и «даже спала в кабинете великого князя на диване».

Однако перед тем как пойти на такой серьёзный шаг, как женитьба, Великий Князь Павел Александрович решает привести в порядок свои финансовые дела. На тот момент все его материальные средства в виде денежных сумм и ценных бумаг составляли шесть миллионов золотых рублей. Из этих денег он оставляет себе лишь три миллиона, а остальные размещает в банке, разделив поровну между своими детьми: Великим Князем Дмитрием Павловичем и Великой Княжной Марией Павловной (младшей). Поскольку основная часть капитала Великого Князя представляла собой ценные (процентные) бумаги, их уложили в чемоданы, хранение которых поручили А. А. Волкову. Оставшиеся же денежные средства в виде ассигнаций при посредстве того же А. А. Волкова были перевезены в Германию и размещены в одном из берлинских банков.