Для этого новая экспедиция в составе геодезии-прапорщиков Леонтьева, Лысова и Пушкарева в 1769 году отправилась на Медвежьи острова.
Пять лет геодезисты занимались описанием этих островов, определяли их очертания и размеры. И много раз они пытались проникнуть дальше на север и восток. Однако Земли Андреева им не удалось увидеть ни разу.
Так же неудачно искали Землю Андреева Биллингс и Сарычев. С 1785 по 1793 год они совершали плавание на корабле в восточных водах Северного Ледовитого океана, но не обнаружили никаких следов Большой Земли. Единственное, что оставляло надежду, была запись Г. Сарычева:
«Мнение о существовании матерой земли на севере подтверждает бывший 22 июня юго-западный ветер, который дул с жестокостью двои сутки. Силою его, конечно бы, должно унести лед далеко к северу, если б что тому не препятствовало; вместо того на другой день увидели мы все море, покрытое льдом».
Через несколько десятилетий, в 1810 году, в Нижнеколымск приехал Геденштром. Кроме Земли Санникова, ему нужно было узнать все, что можно, и о Земле Андреева.
Геденштром собирался идти на поиски этой земли не с Медвежьих островов, как делали другие путешественники, а прямо с материка, от так называемого Баранова камня (на карте показан его путь и очертания предполагаемой земли).
Изображение Земли Андреева на карте Геденштрома.
У Баранова камня Геденштрома застигла непогода. Жестокая пурга не утихала целую неделю.
«Наконец, — пишет сам путешественник, — я отправился в море на О (то есть на восток. — С. У.). Проехав 150 верст, начали попадаться нам земляные глыбы на льдинах. Земля сия совсем другого была рода, как находящаяся в ярах матерого берега Сибири. Она совершенно походила на землю Новой Сибири, хотя отдаленность сего места не дозволяла думать, чтобы льдины проходили близ берегов Новой Сибири и срыли с оных сии глыбы. 1 (13) мая видели мы стадо гусей, летевших на NNW (то есть на северо-северо-запад. — С. У.), и белого филина. На севере подымались облака. Глубина морская, измеряемая мною в щелях (трещинах ледяных полей. — С. У.), постепенно уменьшалась. Все сие доказывало близость земли. Но скоро нашли мы непреодолимые препятствия к продолжению пути нашего. В 245 верстах от Баранова камня переехали мы щель в 1 аршин шириною, а в 5 верстах далее достигли щели в 15 сажен».
Казалось, все предвещало землю. Но природа как будто ополчилась на исследователей. Широкие трещины в ледяных полях преграждали им путь. Пришлось отказаться от поисков и вернуться к Баранову камню.
Основываясь на своих личных наблюдениях и прежних сведениях, Геденштром составил карту, на которую нанес причудливые очертания Земли Андреева в восточной части Северного Ледовитого океана. Судя по этой карте, путешественнику оставалось пройти совсем немного, чтобы достигнуть южного выступа этой земли.
Геденштром своими наблюдениями снова подтвердил существование Земли Андреева. Однако основательных доказательств не было: ведь никому не довелось ступить на нее.
Нужна была новая экспедиция. И когда лейтенант Анжу искал Землю Санникова, лейтенант Врангель был послан, как говорилось в инструкции, «для описи берегов от устья реки Колымы к востоку от Шелагского мыса и от оного на север, к открытию обитаемой земли, находящейся, по сказанию чукчей, в недалеком расстоянии».
Врангель дважды отправлялся из Нижнеколымска на север и северо-восток, но никакой земли обнаружить не мог. Он решил попытаться еще раз и снова отправился в путь. Во время этой последней поездки он стал подробно расспрашивать встречных чукчей, не слыхали ли они, что к северу от чукотских берегов есть какая-то земля.
— Есть ли на севере земля? — спрашивает лейтенант Врангель встречных чукчей.
Из рассказов чукчей он выяснил, что «между мысом Ерри (Шелагским) и Ир-Кайпио (Северным), близ устья одной реки, с невысоких прибрежных скал в ясные летние дни бывают видны на севере, за морем, высокие, снегом покрытые горы, но зимой, однако ж, их не видно. В прежние годы приходили с моря, вероятно, оттуда большие стада оленей, но, преследуемые и истребляемые чукчами и волками, теперь они не показываются. По мнению (рассказчика), — пишет далее Врангель, — виденные с берегов горы находились не на острове, а на такой же пространной земле, как его родина. От отца своего слышал он, что в давние времена один чукотский старшина со своими домочадцами поехал туда на большой кожаной байдарке, но что там нашел он и вообще возвратился ли оттуда — неизвестно. Основываясь на том, что с высоты даже Шелагских гор не видно на севере никакой земли, он полагал, что она против того места, где видны высокие, снегом покрытые горы, образует мыс, далеко выдающийся в море».