Среди противников архиепископа выделялся старец Захарий из псковского Немцова монастыря. Владыке стало известно, что Захарий постриг детей боярских «от князя Федора от Бельского да причастия три года не давал, а сам, деи, не причащал же ся». Князь Ф. И. Бельский выехал в Москву из Литвы в 1482 году и вскоре получил во владение городок Демон. Несколько его вассалов нашли прибежище в Немцове монастыре. Будучи вызван в Новгород, Захарий признал вину, но задал архиепископу вопрос: «А у кого, деи, ся, причащати? Попы, деи, по мзде ставлены, и митрополиты, деи, и владыки по мзде же ставлены». Слова чернеца попали не в бровь, а в глаз.
Геннадий обвинил чернеца в ереси, но тот не остался в долгу и назвал еретиком самого архиепископа. Могущественный архиепископ препирался с монахом более трех лет. В 1490 году он жаловался митрополиту на Захария: «Лает ми, господине, бепрестани уже третий год, на четвертой год настало, а посылает грамоты в мою архиепископью, и к черньцом, и к попом семисоборским, а что по Московской земли, то числа нет; а пишет в своих грамотах: послал, деи… на еретика грамоты; а яз не еретик».
Вызывающее поведение Захария объясняется достаточно просто. Чернец жил в Пскове, возглавляя там Немцов монастырь, и хотя псковская епархия подчинялась новгородскому владыке, но в Пскове сохранялись республиканские порядки и под их защитой Захарий чувствовал себя в безопасности. Геннадий объявил Захария стригольником и велел сослать его в заточение «в пустыню на Горнечно». Но Иван III отменил этот приказ и велел отпустить Захария в Псков. Его поступок едва ли был продиктован симпатией к еретикам. Причина заключалась в другом. Псков помог Москве разгромить Новгород, и Иван III подчеркивал, что Псков пользуется его особым покровительством. Избежав заточения, Захарий, не возвращаясь в Псков, уехал в Москву.
Геннадий, попав в Новгород, оказался в явно чуждой ему среде. Новгородцы не желали признавать авторитет московского святителя и честили его как еретика. Памятуя об участи своего предшественника Сергия и стремясь уничтожить своих хулителей, Геннадий организовал суд над новгородскими священниками-еретиками. Поводом к розыску послужил донос о пьяной болтовне двух священников — Григория и Ереса и дьяка Гриди. Вина их заключалась в том, что они «пьяни поругалися святым иконам». Архиепископ Геннадий сам подтвердил, что ересь новгородцев открылась во время пьяной перебранки — виновные «почели урекатися въпиане, и яз послышав то…» После ареста еретиков выдали на поруки, но они сбежали в Москву. На этом дело, может быть, и кончилось бы. Но среди новгородских священников нашелся ренегат поп Наум. Он покаялся, что вместе с беглецами молился «по жидовскы» и прельщал христиан «жидовским десятисловием». Иначе говоря, священники старались, чтобы их прихожане усвоили десять заповедей Моисея — «не убий», «не укради» и другие. Под видом десяти заповедей Ветхого завета священники, как утверждал Геннадий, учили людей богомильству. Затем он отослал донос в Москву, где обвинения против священников были признаны основательными, а в отношении дьяка решено было продолжить розыск. Еретиков под стражей вернули в Новгород и «били по торгу кнутьем». Но и на этом дело не закончилось. Геннадий постарался организовать новый процесс. В ход были пущены жестокие пытки. По поводу этих пыток архиепископ должен был оправдываться в грамоте собору 1490 года. «А яз ли того Самсонка мучил? — писал владыка. — Ведь пытал его сын боярский великого князя, а мой только был сторож». Под пыткой участник пьяной ссоры сын попа Григория дал показания о причастности к ереси видного московского дьяка Федора Курицына, придворных священников протопопа Алексея и попа Дениса и других лиц.
Новгородские наместники Захарьины деятельно помогали Геннадию в борьбе с его недругами-новгородцами, объявленными еретиками. Они лично участвовали в пытках заподозренных новгородцев, снимали допросы. Невзирая на помощь наместников, розыск в Новгороде протекал негладко. Новгородцы искали защиты от своего пастыря у великого князя. Явившись в столицу, они били челом Ивану III «на Генадиа архиепископа о том, что, рекши, он… (их) имал, и ковал, и мучил изо имениа, да грабил животы» их. Корысть, возможно, и была одним из побудительных мотивов Геннадия, поживившегося имуществом еретиков. Но еще более важно для него было другое. Владыка не мог управлять вольным городом, подвергаясь повседневным насмешкам новгородских священников и монахов. Только гонения могли заглушить их голоса.