Тем временем до Петербурга дошли новые вести об открытиях сибирских охотников за мамонтовой костью, обнаруживших острова Васильевский и Семеновский. Решено было отправить экспедицию для точной описи недавно открытых островов и поисков новых земель.
В 1819 году Гавриил Андреевич собственноручно составил "План как производить опись земель, лежавших на Ледовитом море к северу против устьев Яны и Колымы", который хранится в Ленинграде в делах Центрального государственного архива Военно-Морского Флота.
Экспедиция должна была состоять из двух отрядов: колымского и янского. Во время работ исследователям предстояло пользоваться собачьими упряжками. Для этого в Усть-Янске и Нижнеколымске следовало приготовить более двухсот собак и необходимые для их прокормления запасы сушеной рыбы, а на побережье Ледовитого океана построить юрты и амбары, которые служили бы опорными пунктами предстоящих исследований.
Один из отрядов должен был "от Шалацкого Носа чрез море прямо к северу искать землю, о которой сказывали чукчи, что она пространна, находится не в дальнем расстоянии и на ней обитает олений дикий народ".
"Когда сие известие окажется справедливым, — писал Сарычев в своем плане, — то обласкать жителей, познакомиться с ними и постараться описать их земли, но ежели она пространна и невозможно будет описать ее в короткое время, то нельзя ли оставить у тех народов на целое лето двух или трех человек для описи и при собаках, чтоб осенью, когда замерзнет море и утвердится путь, можно было им на тех собаках возвратиться на Колыму. Сей народ, вероятно, должен быть какое-нибудь племя чукчей, удалившееся туда, а потому нужно иметь для объяснения с ними толмача из иричинских казаков, знающих чукуческои язык, а как иные приходят чукчи и в Нижнеколымск, то может быть и там есть толмач сего языка. Когда описатели в одну весну не успеют всего описать, то закончить оное на другой год".
Второй, Янский отряд должен был побывать на Новосибирских островах и предпринять поиски земель, горы которых видели на севере Геденштром и его сподвижник Санников. Этот отряд возглавлял Петр Федорович Анжу. Он нанес на карту все известные земли, но вместо гор, виденных на севере, открыл свободное ото льдов море. Но еще более важными оказались открытия колымского отряда экспедиции, которым руководил 23-летний лейтенант Фердинанд Петрович Врангель. Вместе со своими товарищами он три года настойчиво искал "матерую землю" к северу от Колымы и мыса Шелагского. Но полыньи и открытая вода не давали ему проникнуть далеко в море. Путешественникам, выполнившим исключительно важные исследования на северо-востоке России, не удалось ступить на загадочную сушу. Это было тем обиднее, что встреченные ими чукчи принесли удивительные вести. По их словам, в районе мыса Якан "с невысоких прибрежных скал в ясные летние дни бывают видны на севере, за морем, высокие, снегом покрытые горы…".
Привезенные Ф.П. Врангелем и его товарищами сведения чрезвычайно заинтересовали Сарычева. Рассказы чукчей еще раз подтверждали его давнее предположение о том, что в Студеном море к северу от берегов Чукотки ждет открытия неведомый людям обширный гористый остров. Правда, остров, а не материк. Но все-таки земля к северу от Чукотки существует. Сарычев составил проект новой экспедиции для открытия загадочной земли и представил его на рассмотрение Адмиралтейств-совета. Проект был признан "достойным уважения". Совет решил просить власти Восточной Сибири собрать от чукчей сведения, действительно ли они имеют сообщение с незнаемой землей в Студеном море, а затем уже решить вопрос о снаряжении новой экспедиции.
19 апреля 1828 года морской министр А.В. Моллер по представлению Сарычева направил письмо генерал-губернатору Восточной Сибири А.С. Ловинскому:
"Рассмотрев в Адмиралтейств-совете и найдя достойным уважения представление генерал-гидрографа Морского штаба [4]о том, что имеются некоторые сведения, будто бы чукчи, обитающие на Чукотской земле близь Шелагского мыса, переправляются иногда на землю, лежащую к северу на Ледовитом море и видимую с мыса Якана; а как оные чукчи ежегодно приезжают на оленях в Островную крепость, отстоящую в 250 верстах от Нижнеколымска на ярмарку для торговли, то полагает, что не излишнее было бы снестись по сему предмету с Вашим Превосходительством и просить о предписании, кому найдете нужным, стараться, буде возможно, получить сведения от тех чукочь, действительно ли они имеют сообщение с вышеописанною землею и каким образом переезжают они на оную, то есть: сухопутно ли зимним путем на собаках или оленях или летом водою на чукотских байдарах? — дабы по узнании таковых обстоятельств можно было приступить к назначению экспедиции, как для осмотра и описи той земли, так и для географического определения оной".
Иркутское губернское начальство через полтора месяца уведомило морского министра о том, что необходимые распоряжения сделаны. Сведения предполагалось собрать во время зимней ярмарки в селе Островном, куда ежегодно приезжали чукчи. 4 июня 1829 года в Петербург были присланы, наконец, сведения, полученные при опросе жителей Чукотки. Чаунский тойон Нухай рассказал, что, когда он был еще мальчиком, в один из январских дней "пришли к ним в юрту с Ледовитого моря пешком два незнакомца, имевши по две собаки на поводках, платье имелось на них из оленьих шкур, подобно их чукотскому, с отменой той распестренное разными видами из росомачьих шкур, штаны на них нерпичьи, а обувь из росомачьих лап также распестрена разными видами и разными кистями, из росомачьих же шкур, но токмо довольно уже все то платье на них было поизношено; по приходе ж у женщин просили подобно на киргаульском языке воды и заметя, что не понимают, требование свое повторили на чукотском языке. Вступя в разговор, расспрашивали женщины: отколь к ним пришли, на что отозвались, зашли они к ним с моря от видимой чрез оное земли, быв будто бы втроем и ходив по морю за промыслом, один из них утонул, изъяснились и далее, якобы земля их весьма обширна и велика, даже и пределов ее они не знают и жителей на оной имеется великое множество…".
Тот же Нухай рассказал далее, что больше он не слыхал, чтобы снова зимой приходили люди с неведомой земли в Ледовитом море. Он же поведал, что переправляться по проливу трудно, так как и летом по его волнам носятся льды, а замерзает пролив в январе не более чем на месяц, "иногда гораздо менее, а также другим годом совсем не смыкается". Что касается острова против мыса Якан, то "видна бывает через обширный пролив Земля в апреле последних числах". При этом расспросе присутствовал чукча Гачолен, который сообщил, что на острове имеется камень, подобный столбу.
Восьмидесятилетний чукча Семен Третьяков также определенно заявил, что "действительно есть и видна земля с мыса Якана к северу на Ледовитом море". Кроме того, тойон Ятыргин и почетный чукча Леут удостоверили, что им "известно наверно о земле, видимой с мыса Якана, к северу лежащей…". Ятыргин вместе с тем заметил, что в январе — феврале жители Чукотки неоднократно видели множество диких оленей, переходивших с неведомого острова на "матерую землю". Чукча Инокхей рассказал, что "Землю, лежащую на Ледовитом море к северу в виде гор, весною и летом неоднократно сам видел".
Таким образом, все показания чукчей сводились к тому, что севернее мыса Якан существует земля. Это единодушие очень обрадовало перешагнувшего уже за порог седьмого десятилетия Гавриила Андреевича. Он предпринимал одну за другой попытки добиться снаряжения экспедиции для открытия земли, виденной чукчами. Ему не отказывали категорически, но и не давали средств. Сарычев спешил. Он отправил офицеров для описи берегов Охотского моря вблизи Амура, позаботился об описи Камчатки. Но добиться решения о посылке новой экспедиции для поисков "Северной матерой земли" ему все еще не удавалось. Он требовал, он настаивал. Но дни жизни великого труженика моря были сочтены. В Петербург пришла эпидемия холеры. В числе ее жертв оказался Гавриил Андреевич. Он скончался 30 июля 1831 года в возрасте 68 лет.