Несмотря на близость Матвеева к Петру и на личное участие царя в деле о снаряжении посольства в Голландию, приказная машина в Москве работала по обыкновению медленно, с задержками и взаимным сваливанием вины в этой задержке одними приказами на другие. Перед самым отъездом посольства, в начале августа 1699 г., начальник Большой казны князь П.И. Прозоровский отказал посольству в выдаче прогонных денег, которые оно рассчитывало получить из этого приказа, так что Матвеев принужден был обратиться с жалобой к начальнику Посольского приказа Льву Кирилловичу Нарышкину и просить его содействия. «Премилостивой батко и государь мой Лев Кириловичь, – писал он ему в письме, – выну (sic) радостно о Господе здраствуй. Горько слезную мою просьбу к тебе, государю моему, доношу и самую остановку надлежащего мне в предприятый путь мой объявляю дела. Продержав меня, князь Петр Иванович Прозоровской до сих часов по памяти из Посолского приказу в прогонных всех денгах отказал и память с отповедью из приказу Болшие казны в Посолской приказ велел послать, что никому посолским персонам из того приказу не давано, а всегда даваны из того приказу, от-куду посылка, и прежде бывшим послом даны из Посолского приказу, также и господину Украинцеву, а не из Болшие казны прогоны. А ныне, премилостивой государь мой, сугубые из того напасти спеют: первое, от того неотпуска своего государева гневу опасен, а я не за свою волю коснею; второе, и время летнее тратится, чтоб не испустить его и горших убытков, паче же самого безпутства (т. е. порчи дорог) не принять и бедства. Сотвори, премилосердый государь мой, милость последнюю со мною, рабом своим, и не отпусти меня в таковой дальний путь с горестию и слезами от милости своей. Прикажи из каких возможно доходов те прогоны выдать из Посолского или из Новгородского приказов без задержания и указ свой с подкреплением к дьяком послать, потому что и так они, один на одного перепираяся, и по се число во всем том задержание в настоящее мое дело чинили, чтоб, премилостивой государь мой, выбресть мне при помощи Господни безотложно завтрашнего дни впредь приспетой тот путь мой. И чтоб те прогоны по прежнему указу твоему, государя моего, и милостивому твоему слову в оба пути были выданы; если ныне мне по твоей, государя моего, милости при себе не выходить, впредь чрез писма свои получить будет зело трудно. Также и тем не повели впредь в сем мною образца учинить.
К сему милости прошу к Кирилу Алексеевичу [Нарышкину