До этой далекой земли сержант Андреев не добрался, ибо «за долговременным осмотром островов и за одержимыми в море пургами весьма сделалось собачьими кормами скудность». И хотя сержант «усердно и ревностно желал и понуждал команду ехать далее в море, токмо команда единогласно стали говорить, что далее следовать в море оставить».
По приказу Плениснира Андреев с пятью казаками направился на следующий, 1764 год вновь на Медвежьи острова. Взойдя на вершину горы Четырехстолбового острова, Андреев увидел в ясный солнечный день ту же «синь», или «чернь», и он и его люди «дались на усмотренное место».
Пять суток длился пробег на санях по замерзшему Студеному морю. А на шестые сутки пути, ранним утром, путники увидели «остров весьма немал. Гор и стоячего лесу на нем не видно, низменной, одним концом на восток, а другим — на запад, а в длину так, например, быть имеет верст семьдесят». Андреев и его люди направились к «западной изголовье» острова, однако, «не доезжая того верст за 20, наехали на свежие следы превосходного числа на оленях и на санях неизвестных народов, и, будучи малолюдны, возвратились в Колыму».
Плениснир, получив отчет Андреева, сообщил о его открытии губернатору Сибири, в Академию наук и в личный кабинет императрицы Екатерины II. Кроме того, он составил, по рассказам чукчей, «скасок» промышленников и рапортов сержанта Андреева и чукчи Дауркина чертежи Чукотской вемли. Там показаны Медвежьи острова, Земля Андреева на восток от них, фантастические очертания «Американской матёрой со стоячим лесом земли» и земли Китиген (или Тикиген), на которой живут «оленные люди хрохай».
Плениснир за свои открытия получил чин полковника, а сержант Андреев «за понесенные двухгодичные труды» был произведен в подпоручики. Спустя пять лет для наведения контактов с «оленными людьми» и описания Земли Андреева отправились три прапорщика-геодезиста Иван Леонтьев, Иван Лысов и А. Пушкарев. В марте — апреле 1769 года они на собаках перебрались из Нижнеколымска на Медвежьи острова и сделали их съемку (ибо сержант Андреев «по незнанию наук какое положение они имеют на карте изъяснить не мог»), В феврале 1770 года геодезисты из Нижнеколымска добрались до самого восточного из Медвежьих островов и двинулись на поиски Земли Андреева. Около трехсот километров проделали они по льду, но никакой суши обнаружить не смогли.
Три центральных острова, расположенных меридионально, тщательно изученные и заснятые молодыми прапорщиками-геодезистами, справедливо получили наименования Пушкарева, Леонтьева, Лысова в группе Медвежьих островов. Но Земля Андреева, которую они не смогли обнаружить, оставалась загадкою: выяснилось, что при ее поиске геодезисты, руководствуясь неточной картой, составленной Пленисниром, искали Землю Андреева в северо-восточном направлении, в то время как искать ее следовало на северо-западе.
В 1785 году северо-восточные берега Сибири исследовала экспедиция под началом Биллингса и Сарычева. Сарычев записал В судовом журнале, что, когда корабль под его началом стоял у Баранова Камня, готовясь пробиться сквозь льды, ледовая обстановка говорила о том, что неподалеку должна быть какая-то суша: «Мнение о существовании матерой земли на севере подтверждает бывший 22 июня юго-западный ветер, который дул с жестокостью двои сутки. Силою его, конечно бы, должно унести лед далеко к северу, если б что тому не препятствовало. Вместо того на другой же день увидели мы все море, покрытое льдом. Капитан Шмелев сказал мне, что он слышал от чукоч о матерой земле, лежащей к северу, не в дальнем расстоянии от Шелагского Носа, что она обитаема и что шелагские чукчи зимнею порою в одни сутки переезжают туда по льду на оленях». Однако достичь этой обитаемой и «матерой», то есть не сложенной льдами, земли ни Сарычев, ни Биллингс не смогли.
Весной 1810 года на пяти нартах из Нижне-Колымска к Баранову Камню отправился Геденштром, посланный для исследования островов между устьями Лены и Колымы. Переждав буран, длившийся неделю, он отправился на пяти нартах по льдам, сковывавшим море, на северо-восток. «Проехав 150 верст, — сообщал Геденштром, — начали попадаться нам земляные глыбы на льдинах. Земля сия совсем другого была рода, как находившаяся в ярах матерого берега Сибири. Она совершенно походила на землю Новой Сибири, хотя отдаленность сего места не позволяла думать, чтобы льдины проходили близ берега Новой Сибири и срыли с оных сии глыбы. 1 мая видели мы стадо гусей, летевших на север-северо-восток, и белого филина. На севере поднимались облака. Глубина морская, измеряемая мною в щелях, постепенно уменьшалась. Все сие доказывало близость земли. Но скоро нашли мы непреодолимые препятствия к продолжению пути нашего. В 245 верстах от Баранова Камня переехали мы щель в 1 аршин ширины, а в пяти верстах далее достигли щели в 15 сажен. На пяти верстах сих глубина морская от 11 с половиной саженей уменьшилась до 11 саженей».
Полыньи и торосы преградили путь Геденштрому. К тому же кончались запасы продовольствия, взятые на двадцать дней, из которых семь пришлось на пережидание бурана. Исследователь был вынужден повернуть обратно, хотя уверенность его в реальности острова в океане была столь велика, что Геденштром нанес Землю Андреева на карту.
В 1820 году «для описи берегов от устья Колымы к востоку до Шелагского мыса и от оного на севере к открытию обитаемой земли, находящейся, по сказанию чукчей, в недалеком расстоянии», была направлена экспедиция под командованием двух лейтенантов флота — Фердинанда Петровича Врангеля и Петра Федоровича Анжу (последнему было поручено описание побережья в районе устьев рек Оленек, Лены и Яны, а также Новосибирских островов).
Лейтенанту Врангелю обнаружить Землю Андреева к северу от Колымы не удалось. Он решил, что этой земли никогда и не было. Тем не менее в 1823 году, когда, завершилась экспедиция Врангеля и Анжу, в журнале «Сибирский вестник» появилась публикация, согласно которой Землю Андреева видел не только сержант Андреев: «Другие известия доказывают, что сия земля имеет жителей, которые называют ее Тикиген, а сами известны под именем хрохаев и состоят из двух племен. Некоторые из них бородатые и похожи на россиян, другие же чукотской породы. Бывшие при экспедиции Биллингса сотник Кобелев и толмач Дауркин подтвердили описание Андреева, представили даже абрис виденной ими земли».
Таким образом, помимо загадки Земли Андреева возникла еще и загадка обитаемой Земли Тикиген или Китиген с ее племенем «оленных людей хрохай»: является ли она той самой землей, что видел сержант Андреев, или же это еще один остров в Ледовитом океане. Либо, что также требовало проверки, и Земля Андреева, и Земля Китиген — плод воображения, а не реальные острова на север от устья Колымы.
Найти эти острова пытались русские ледоколы «Таймыр» и «Вайгач» в начале нашего столетия. Вместо этого «Вайгачу» удалось впервые обойти и описать северный берег острова Врангеля в поднять на нем русский флаг, а вслед за тем, в 1913 году, обогнув мыс Челюскина, «Вайгач» и «Таймыр» открыли предсказанную гениальным П. А. Кропоткиным Северную Землю, на берегах которой был также поднят флаг России. Но Земли Андреева ледоколам «Вайгач» и «Таймыр» обнаружить не удалось.
Землю Андреева пытался найти спустя два десятка лет пароход «Челюскин», но натолкнулся в районе поисков на непроходимые льды. Сквозь эти льды пробился позднее ледокол «Красин», однако ему также не удалось обнаружить какую-либо землю на север от устья Колымы. В 1935 году полярный летчик В. С. Молоков попытался найти Землю Андреева с воздуха, однако так и не увидел ее. В 1943 и 1946 годах корабли экспедиции Арктического института проникли на север и северо-запад от маршрута «Красина», однако и здесь, уже почти в самом сердце Арктики, никакой земли не обнаружили.
Что же тогда видел сержант Андреев? Подлинные его записи долгое время считались утерянными. И, как совершенно справедливо писал известный советский полярник В. Ю. Визе, предсказавший на основании точных научных расчетов существование острова в Карском море, названного его именем, «до тех пор, пока не найдутся журналы, веденные Андреевым в 1764 г., нет достаточных оснований к тому, чтобы порочить имя этого скромного исследователя прозвищем обманщика и лжеца».