В частных письмах своих к его старому покровителю и интимнейшему другу генералу Клюки фон Клугенау, стоявшему с дивизией в Царстве Польском, Евдокимов 17 августа 1850 года писал между прочим[47]: «Прибыв из Дагестана на пути к новому назначению в Ставрополь, я встречен был известием о волнениях в крае, произведенных Магомет-Эмином, агентом Шамиля, и сборах значительных неприятельских партий, вследствие чего командующий войсками предложил мне торопиться к месту, и на другой день прямо через Прочный Окоп я уже очутился на Лабе, через которую 23 апреля переправился для прикрытия покорных нам темиргоевцев. Не найдя ни малейшего устройства в делах фланга, мне пришлось увидеть себя в самом затруднительном положении, в крае, мне незнакомом, однако надо было действовать, и я проводил в трудах и дни, и ночи». Далее: «После отражения второго покушения на нашу линию Магомет-Эмин отправился покорить своей власти шапсугов и оставил меня в покое, но я уже был болен: лабинский нездоровый климат подействовал на меня так неблагоприятно, что меня едва довезли до Прочного Окопа, затем желчные припадки до того усилились, что я, бросив свой пост, уехал в Кисловодск, где оставался три недели и благодаря климату и советам доктора Андреевского поправился, а 13 августа возвратился к месту. Назначением своим, – продолжает Евдокимов, – я похвалиться не могу. Кордон по Кубани, Лабе и в верховьях этих рек составляет более 700 верст; мне предстоит оборонять эту линию с 12 полками, казаков, из коих четыре рассыпаны на внутренних постах и по почтовому тракту, да с восемью батальонами пехоты, большая часть коих должна занимать гарнизоны в станицах и укреплениях по Лабе. С большим трудом и с опасностью для некоторых пунктов имею возможность сосредоточить от 10 до 12 рот и до 2 тысяч кавалерии, но, не отдаляясь от пехоты, я не могу предупреждать неприятеля на таком огромном пространстве, а неприятель в 6 или 7 тысяч лучшей конницы может бросаться на любой пункт и, конечно, не туда, где есть в готовности наши войска. Угадать намерение неприятеля – дело весьма трудное, лазутчиков теперь почти нет, Магомет-Эмин их убивает, да и вообще доставлять удовлетворительные известия сделалось невозможным, потому что власть Эмина до того усилилась, что залабинские черкесы, подобно дагестанским горцам, идут туда, куда им приказано, не зная сами, для какой цели. Словом сказать, Магомет-Эмин становится вторым Шамилем… На мне лежит теперь бремя защиты слабой страны со слабыми средствами, и я часто задумывался над возможностью переменить место службы… Кавказ удостаивается в нынешнем году посещения Государя Наследника, и мы все теперь озабочены приготовлениями для встречи. Слава Богу, дарующему мне случай увидеть одну из наших царственных особ. Петербург от нас далек, человеку небогатому трудно туда попасть, и если уже суждено лечь моим костям в степях Кавказа, то все же отрадно для русского сердца увидеть хоть одного из тех, которых мы привыкли чтить владыками нашей земли. Его Высочество будет в Екатеринодаре и выезжает оттуда по Лабинской линии до Прочного Окопа через Пятигорск и Владикавказ в Тифлис».