В
этимологическом словаре Фасмера написано, что _ненавидеть_ восходит к более древней форме _ненавидти_, которая была образована с отрицанием от _навидти_ "охотно смотреть, навещать".
Похожая ситуация с прилагательным _неуклюжий_. Когда-то было такое прилагательное -- _уклюжий_ ("стройный", "ловкий", "ладный"), но вышло из употребления (хотя во многих словарях пока что есть) , а _неуклюжий_ почему-то осталось.
Я бы это объяснил тем, что в языке есть стремление разграничивать, разводить в разные стороны слова, обладающие противоположным или принципиально отличным смыслом. Например: друг -- враг (враг используется чаще, чем недруг) , хороший -- плохой (нехороший используется только для отрицания "хорошести"). Если прилагательное с частицей не- активно используется (и уже не осознается как отрицание некого качества или свойства) , есть вероятность, что со временем исходная форма без частицы не- может выйти из активного употребления, а со временем и устареть.