За время пребывания в Средиземном море, В. Истомин не раз бывал со шхуной на Мальте, в Адриатике, избороздил греческий Архипелаг.
Зимой 1840 года «Ласточка» возвратилась в Севастополь, и вскоре её экипаж включился в подготовку к очередной десантной операции на Кавказ. Уже в марте 1840 года «Ласточка» в составе эскадры контр-адмирала Станюковича, погрузив часть десанта, отправилась в Феодосию. В десантной операции у Туапсе шхуне «Ласточка» предписывалось действовать на левом фланге десанта. Участвовал в высадке десанта 20 мая и брат В. Истомина, адъютант Лазарева, Гвардейского экипажа капитан-лейтенант Константин Истомин. Десантная операция прошла успешно, на берег было высажено 9000 человек с артиллерией, боезапасами, провизией.
На шхуне «Ласточка» износились паруса, и её отправили в Николаев обновить снаряжение.
Лазарев, скупой на похвалу, по достоинству оценил службу В. Истомина, вскоре посылает рапорт Меншикову о повышении в должности и звании.
«Лейтенанта В. Истомина, в. с-ть непременно произвели бы сами, если бы увидели возвращение в зимнее время шхуну „Ласточку“; описываемые мне в партикулярном письме Катакази отзывы о ней англичан и французов, командовавших военными судами в Архипелаге, и в особенности флота капитана Лайонса, возвышают честь российского флота за границей… Истомин восьмой год как служит лейтенантом и 13 лет — офицером, я намерен представить в. св-ти о назначении его командиром на имеющей заложиться послезавтра корвет и в таком случае чин капитана-лейтенанта очень соответствовал бы таковому командованию. Познания его и заботливость по службе доставят флоту отличнейший корвет».
В июле 1840 года Истомин произведён в капитан-лейтенанты и назначен командиром корвета «Андромаха».
Две кампании «Андромаха» с перерывами на ремонт и отдых экипажам крейсировала в Абхазской экспедиции у берегов Кавказа. Турецкие контрабандисты в эту пору присмирели, не решались действовать в открытую, использовали непогоду и тёмными ночами под берегом иногда ускользали от дозоров. Вовсе прекратили свои визиты английские лазутчики, так как Лазарев решительно пленил их суда без оглядки на Петербург. Другое дело, что на побережье горцы продолжали частыми набегами на укрепления наносить иногда значительный урон войскам. Тогда армейские начальники обращались за помощью к морякам.
В 1844 году корабли флота для усиления армии на Кавказе переправили через Керченский пролив пехотную дивизию. С приходом нового командующего, наместника на Кавказе, генерала Воронцова, действия против горцев активизировались. Для налаживания более тесного взаимодействия с войсками Лазарев назначил В. Истомина своим представителем при ставке наместника:
— Поимейте в виду, Владимир Иванович, — наставлял Лазарев перед убытием Истомина, — Воронцов вояка стрелянный со времён Наполеона. Потому Старайтесь лицом в грязь не ударить. Впрочем, вы дипломатии в Греции обучились.
Три с лишним года провёл Истомин в ставке Воронцова. Приходилось ему не только обеспечивать взаимодействие войск на Кавказском побережье, но и сопровождать Воронцова на Каспий, где он начал операцию против Шамиля. Но связи с флотом Истомин не порывал, о чём свидетельствует его переписка с Лазаревым.
Лазарев благодарит Истомина за сведения о Каспийском театре, старается подбадривать его в борьбе с местными казнокрадами:
«Честность, самолюбие и деятельность, соединяясь вместе, расторгают всякие преграды, и никакая бестия против них не устоит».
Лазарев сообщал Истомину о всех важных событиях флотской жизни, о строительстве офицерского собрания, о восстановлении Морской библиотеки. Не забывает и о дружбе Истомина с Нахимовым. «„Кагул“ назначен в Абхазский отряд, и на нем пойдёт П. С. Нахимов. Может быть, вы там его увидите».
«Зимой 1848 года в Новороссийской бухте, во время жестокого урагана, бури, — Лазарев делился своими переживаниями за утраты, — выкинуло на берег корвет „Пилад“, бриг „Паламед“, пароход „Боец“ и транспорт „Гостогай“, а тендер „Струя“ затонул на бриделе со всем экипажем, командиром и офицерами! Подобного ужасного случая никогда ещё не было… Бедная „Струя“! Если бы он догадался отдать ночью свои цепи у бочки, то хоть и разбило бы его на берегу, но спаслись бы люди! Если ко всему этому, т. е. к ужасному этому урагану, прибавлю вам, что морозу тогда было -14°, то вы можете представить себе, в каком положении суда наши в Новороссийске находились и что они вытерпели! Многие из офицеров и нижних чинов остались с отмороженными членами!..»
Истомин в курсе всех событий на флоте. Получив от Лазарева известие о закладке новых кораблей, он отвечает: «Я был душевно рад прочесть, что взамен „Варшавы“ заложен 120-пушечный корабль „Париж“ и что он строится по плану „Двенадцати апостолов“.