Относительная стабильность наступила лишь тогда, когда лайн-ап приобрел форму дуэта: Скотт "Халлхаммер" Халл (гитара, бас, драм-программинг) и Джей Рэндолл (вокал). Покончив на время с кадровыми вопросами, группа занялась записью всевозможных сплитов, где компанию им составили другие грайндкорщики типа "Benumb", "Converge", "Cattlepress" и "Laceration".

В 1998-м "Agoraphobic Nosebleed" заключили контракт с "Relapse Records" и дебютировали с альбомом "Honkey Reduction". 26 треков общей длительностью 19 минут представляли собой маниакальный грайнд, режущий плоть и приводящий мозги в состояние "всмятку". Второй мощный удар по сознанию мирных граждан был нанесен в конце 1999 года, когда на свет появилась шестидюймовка "PCP Torpedo", с помощью которой "ANb" окончательно смели все преграды на пути к сумасшествию. Однако лейблу показалось этого мало и они свели "Agoraphobic Nosebleed" с бостонскими экстремальщиками "Converge" для работы над совместным альбомом "The Poacher Diaries".

Как ни странно, но "Молотов-коктейль", изготовленный этими командами, вызвал положительные отклики (правда, у самых отчаянных фанатов грайнда). "Relapse Records", похоже, обрадовались этому факту и под самый занавес 1999-го выпустили еще один сплит "ANb" – с "Benumb".

Когда музыканты начали работать над новым полнометражным альбомом, решено было сделать значительный шаг в сторону утяжеления саунда, что в свою очередь потребовало дополнительных человеческих ресурсов. Для решения вопроса к делу были привлечены опытные мастера грайнд-сцены, Ричард Джонсон из "Enemy Soil" и Карл Шульц из "Prosthetic Cunt". Процесс создания "Frozen Corpse Stuffed with Dope" растянулся на целых три года, но после выхода диска в свет музыканты были вознаграждены теплым приемом. При этом лестные отклики последовали не только со стороны упертых фанатов грайнда, но и со стороны таких уважаемых изданий как "Rolling Stone", "Alternative Press", "Kerrang!", "Terrorizer", "Washington City Paper" и некоторых других. В ответ на положительные рецензии "Agoraphobic Nosebleed" со свойственным им цинизмом решили поиздеваться над публикой и 1 апреля 2003-го выпустили трехдюймовый компакт "Altered States of America", на который запихали целых сто(!) треков.

В том же году впервые состоялось появление "ANb" на публике – в рамках "New England Metal and Hardcore Festival" команда отыграла пару своих песенок. Спустя пару лет группа порылась в запасниках "дорелапсовского" периода и наскребла материала аж на целых два компакта, изданных как "Bestial Machinery (Discography Volume 1)".