Замечу в качестве отдельного наблюдения, что "всегда не" абсолютно не сочетается с глаголами совершенного вида. А "никогда не" с такими глаголами в разговорной речи встречается повсеместно (в художественной литературе редко, но в принципе считается допустимым).
Далее, мне удалось найти небольшое обсуждение этого вопроса во втором томе избранных трудов Ю.Д. Апресяна. Там указывается, что этот вопрос сложен и рассматриваются только его отдельные моменты. Я приведу выборочно пару цитат, не пытаясь дать полный связный ответ на поставленный вопрос.
Те же рассуждения в принципе верны и для ГСП (глубинно-синтаксическое
представление). ГСП предложения Иван всегда не ездит на такси
абсолютно неправильно, потому что в нем нарушен некий сочетаемостный
запрет, состоящий в самом первом приближении в том, что общекванторное
слово (везде, все, всегда, всякий) не сочетается с не, если оба эти
слова зависят, непосредственно или опосредствованно, от одного и того
же предикатного слова.
(Сноска к сказанному выше.) В действительности запрет носит
гораздо более сложный характер, особенно если учесть факторы (см.
раздел 4.3), от которых мы в этой работе решили отвлечься. Фразы типа
Всегда он не просыпается во время (с логическим ударением на общекванторном слове) допустимы в большей мере, чем фразы типа Он
всегда не просыпается во время (без логических ударений). В
противопоставительном контексте комбинация всегда не
представляется более допустимой, чем в нейтральном контексте; ср.
Иван всегда не спит, когда другие давно спят. Некоторые другие тонкости, связанные с употреблением слов этого типа в контексте
частицы не, обсуждаются в следующих работах: Seuren P. A. М.,
Negative's Travels, в: Semantic Syntax, Edited by Pieter A.V.Seuren,
Oxford, 1974. С. 197; Падучева Е. В. О семантике синтаксиса. Материалы
к трансформационной грамматике русского языка. М., 1974, С. 108-109.
Выскажем одно несогласие. Е. В. Падучева считает, что всегда
преобразуется в никогда "в контексте грамматического отрицания" и
говорит о "замещаемости слова всегда словом никогда" (С. 108),
называя их "контекстными синонимами". Это представляется нам
неточностью: не при всегда и при никогда выполняет
совершенно разные роли — смысловую в первом случае и чисто
грамматическую (своего рода согласовательную) во втором. Отрицание не
может поэтому рассматриваться как один и тот же элемент контекста.
Всегда и никогда — не синонимы, а антонимы. Отношение синонимии имеет место только между "словосочетанием" всегда не (со
смысловым не!) и словом никогда (см.об этом Апресян Ю. Д. Цит.
соч., С. .296, 331). В связи со сказанным в формальной модели лучше
иметь не одну трансформацию (всегда <=> никогда в "контексте
грамматического отрицания"), а две разных: 'всегда не' <=>
никогда (на этапе СемП <=> ГСП) и никогда <=> никогда не.
Заметим, в частности, что хотя русские слова всегда и не при
определенных условиях не сочетаются друг с другом, т. е. дают
неправильное ГСП, семантические слова (смыслы) 'всегда' и 'не'
в соответствующем СемПе идеально сочетаемы. Об этом свидетельствуют
безупречные в языковом отношении фразы типа Петр всегда отсутствует:
отсутствовать ='не присутствовать' и, следовательно, Петр всегда
отсутствует = 'Петр всегда не присутствует'.