Верно ли, что слово "невежи" образовалось от "не ведьмы", или у него другое происхождение?

нет
ведьмы - эти от слова ведать (знать) дескать ЗНАЮЩИЕ
а невежа - все-таки вроде бы от слова ВЕЖЛИВОСТЬ, то есть невежливый, неблагодарный
а еще есть подобное слово НЕВЕЖДА - вот это как раз о человеке темном как три подвала :-)

может КОГДА-ТО они и были однокоренными, но потом значения разошлись

Считайте, что для Вас слова "невежа" и "невежда" происходят от слова "не въезжать", это наиболее соответствующий истине вариант.

невежа сущ
Искон. Преф. производное от вежа - «знаток» . См. вежливый, ведать.
Это Вам от товарища Даля...)))

Слово невежа происходит от церк. -слав. невѣжда (др. -греч. ἀγνώστης). Из не- и *vědi̯ā от ведать. Ведать ст. -слав. вѣдѣти, русск. ведать, т. е. знать. Толково-образовательный словарь говорит, что это слово значит не знающий приличий, грубый, неучтивый человек. Что касается невежДы, то это малообразованный человек, а также человек, несведущий в какой-н. области.
Современная семантическая дифференциация слов невежда и невежа — продукт послепушкинской эпохи. Синонимы высокого слога — невежда и простого — невежа не различались в языке XVIII и начала XIX вв. по своим предметным значениям.

сколько я помню старославянский, веди -знать, знание, неведи-невежа-незнающий

Вежи-ведающие, знающие. Соответственно невежи - не знающие. Ведьма-тожже от этого корня. Ведунья.

а я думаоа, что от слова вежливость, ну может я и ошибаюсь, я не сильна в этимологии русскоязычных слов