Однако геодезисты в своих поисках руководствовались неточной картой Плениснира и искали Землю Андреева в северо-восточном направлении, в то время как искать ее следовало на северо-западе. В 1785 году Гавриил Сарычев, исследуя северо-восточные берега Сибири, записал в судовом журнале, что, когда корабль стоял у Баранова Камня, ледовая обстановка говорила о том, что неподалеку должна быть какая-то суша: «Мнение о существовании матерой земли на севере подтверждает бывший 22 июня юго-западный ветер, который дул с жестокостью двои сутки. Силою его, конечно бы, должно унести лед далеко к северу, если б что тому не препятствовало. Вместо того на другой же день увидели мы все море, покрытое льдом. Капитан Шмелев сказал мне, что он слышал от чукоч о матерой земле, лежащей к северу, не в дальнем расстоянии от Шелагского Носа, что обитаема и что шелагские чукчи зимнею порою в одни сутки переезжают туда по льду на оленях».
Но обнаружить эту обитаемую и «матерую», то есть не сложенную льдами, землю не удалось, так же как и не нашел земли в районе Баранова Камня М. М. Геденштром, исследовавший острова между устьями Лены и Колымы. «Проехав 150 верст, — сообщал Геденштром, — начали попадаться нам земляные глыбы на льдинах. Земля сия совсем другого была рода, как находившаяся в ярах матерого берега Сибири. Она совершенно походила на землю Новой Сибири, хотя отдаленность сего места не позволяет думать, что льдины проходили близ берега Новой Сибири и срыли с оных сии глыбы. 1 мая видели мы стадо гусей, летевших на северо-северо-восток, и белого филина. На севере поднимались облака. Глубина морская, измеряемая мною в щелях, постоянно уменьшалась. Все сие доказывало близость земли. Но вскоре нашли мы непреодолимые препятствия к продолжению пути нашего». Путь Геденштрому преградили торосы и полыньи, и он был вынужден повернуть обратно, хотя уверенность его в реальности земли была так велика, что Геденштром нанес на карту Землю Андреева.
В 1820 году «для описи берегов от устья Колымы к востоку от Шелагского мыса и от оного на севере к открытию обитаемой земли, находящейся, по сказанию чукчей, в недалеком расстоянии», была направлена экспедиция под командованием двух лейтенантов флота — Ф, П. Врангеля и П. Ф. Анжу. Обнаружить Землю Андреева им не удалось — и тем не менее в том же 1823 году, когда закончилась экспедиция, в журнале «Сибирский вестник» вышла публикация, из которой следовало, что эту землю, помимо Андреева, видели и другие люди. «Другие известия доказывают, что сия земля имеет жителей, которые называют ее Тикиген, а сами известны под именем хрохаев и состоят их двух племен. Некоторые из них бородатые и похожи на россиян, другие же чукотской породы. Бывшие при экспедиции Биллингса сотник Кобелев и толмач Дауркин подтвердили описание Андреева, представили даже абрис виденной ими земли».
Но тщетны были поиски Земли Андреева и в прошлом, и в нынешнем веке. Ни ледоколы, ни самолеты, с борта которых велся поиск, ее не обнаружили. Не менее загадочно исчезновение другой земли — Земли Санникова.
В 1805 году, во время летовки на острове Котельном, Санников видел к северу от него высокие горы неведомой земли. В следующем году он заметил с «Высокого мыса» еще одну землю, точнее, «синеву», говорящую о том, что где-то на северо-северо-востоке должна быть суша. Когда в 1810 году Геденштром приехал описывать острова Новосибирского архипелага, Санников сообщил ему, что с северо-западного берега острова Котельный «в примерном расстоянии 70 верст видны высокие каменные горы». Синеву, «совершенно похожую на отдаленную землю», видел и сам Геденштром, стоя на Каменном мысу острова Новая Сибирь. Геденштром отправился к этой земле по льду, но огромная полынья помешала ему, и в зрительную трубу он смог только различить «белый яр, изрытый множеством ручьев». Но на следующий день оказалось, что это не земля, а «гряда высочайших ледяных громад».
На проверку сведений Санникова была направлена экспедиция под началом лейтенанта (впоследствии адмирала) Петра Федоровича Анжу. За два года, с 1821 по 1823, экспедиция Анжу описала северное побережье Сибири между реками Оленек и Индигирка и Новосибирский архипелаг. Сам Анжу прошел зимой на собаках около 10 тысяч километров, а летом на лошадях или с помощью лодок преодолел около четырех тысяч километров. Им был открыт небольшой остров Фигурина и северный берег острова Котельный. Никаких земель в океане к северу от последнего лейтенант Анжу не увидел. Тогда он двинулся по льду на северо-запад, прошел свыше 40 верст, но и ему преградила путь все та же огромная полынья, что мешала Санникову и Геденштрому.
Земли, однако, видно не было. И Анжу решил, что Яков Санников видел лишь «туман, похожий на землю». Зато с северо-западного мыса острова Фаддеевский Анжу, как и Санников, различил синеву, «совершенно подобную видимой отдаленной земле». Четко виднелись и следы оленей, которые ушли по направлению к этой синеве. Но и на сей раз полынья преградила путь исследователям.