Перед отплытием Николай Николаевич тщательно осмотрел берега Петропавловской гавани и сам наметил наиболее удобные места для установки батарей. Здесь же решился и вопрос о кандидатуре будущего камчатского губернатора. Он был решен в беседе Муравьева с архиепископом Камчатским и Алеутским Иннокентием Вениаминовым. Вдвоем они пришли к выводу, что наилучшим кандидатом на этот пост будет Василий Степанович Завойко, а не Иван Васильевич Вонлярлярский, который был вначале у Муравьева на приеме. С 25 июля по 2 августа пробыл Муравьев в Петропавловске и окончательно решил вопрос о перенесении российского тихоокеанского порта. А Екатерине Николаевне Камчатка настолько понравилась, что она высказала желание поселиться тут навсегда. "По крайней мере, — добавила она, — после отставки мужа".
Перед уходом в плавание к берегам Сахалина Муравьев послал Л.А. Перовскому письмо-представление, в котором наметил программу преобразований здешнего края. Он предлагал упразднить Охотский порт и перевести его в Петропавловск. Одновременно следовало упразднить также и Охотское приморское управление, а входящие в него округа подчинить: Охотский — Якутскому областному начальнику, а Гижигинский — Камчатскому военному губернатору. Камчатскую область с присоединенным к ней Гижигинским округом возвести в ранг губернии и назначить военным губернатором моряка, причем именно В.С. Завойко, с присвоением ему чина контр-адмирала. Муравьев считал необходимым построить в Аяне порт Российско-Американской компании. Намечал он также переселить на Камчатку и в Охотский край до трех тысяч семейств русских земледельцев, перечислял необходимые меры для укрепления Авачииской губы и охраны прилегающих морей от иностранных китобоев.
Возвращаясь на "Иртыше" из Петропавловска в Аян (а он решил возвращаться не через Охотск, а через Аян, дабы осмотреть и этот порт), генерал-губернатор почти наверняка рассчитывал встретить в море Корсакова па "Кадьяке", а может быть, и самого Невельского на "Байкале". Но по выходе из Авачииской губы мореплаватели попали в штиль, который задержал продвижение почти на десять суток. И при этом стояла жестокая мертвая зыбь, от которой досталось всем, а более всего, конечно, женщинам. Не помогло даже искусство опытного капитана, каковым, несомненно, был В.К. Поплонский, — транспорт качало неимоверно. Уйти от этой качки помог бы только ветер, а его не было.
Затем долго и безуспешно искали встречи с русскими кораблями, но в большом количестве встречали лишь иностранных китобоев. "Кадьяка" и "Байкала" нигде не было. Сначала пошли к Сахалину. "Иртыш" лег в дрейф между траверсами мысов Елизаветы и Марии. 22 августа на берег отправились Ваганов, Струве и Штубендорф. Ваганов произвел глазомерную съемку местности, Штубендорф занимался сбором трав, растений, камней, а Струве выменивал у местных жителей гиляков (нивхов) свежую рыбу и расспрашивал о "Байкале", но так и не узнал ничего. После возвращения посланцев на борт "Иртыша" Муравьев приказал идти к Шантарским островам. Там тоже высаживались на берег. Но и на Шантарах Невельского не оказалось, и никто из местных жителей ничего о нем не слыхал.
"Генерал-губернатор был этим очень недоволен, — вспоминал Струве, — и мы вошли в порт Аян в весьма невеселом настроении духа. Это тяжелое настроение еще усугубилось встречею в Аяне с М.С. Корсаковым, который донес о безуспешности своего плавания, и предположением вследствие всего этого, что "Байкал", вероятно, погиб или на пути из Петропавловска, или в Амурском лимане, окруженном, по сведениям В.С. Завойко, опасными банками". Почти двухмесячное плавание Корсакова по Сахалинскому заливу, в районе Шантарских островов и по Тугурскому заливу, во время которого русские моряки неоднократно высаживались на берег, не привело к встрече с Невельским. И Корсаков вынужден был возвращаться в Аян, так и не исполнив своего поручения. Это было в самом начале августа. "Кадьяк" вскоре ушел в Охотск, а Корсаков остался в Аяне у В.С. Завойко ожидать прибытия Муравьева. Василий Степанович сообщил Корсакову, что он со своей стороны послал навстречу "Байкалу" своего подчиненного Д.И. Орлова на байдарах и поручил ему сообщить его командиру последние известия: Муравьев на Дальнем Востоке, а Невельского ищут, чтобы вручить инструкцию.