Давайте разберемся.
С.И. Ожегов, Н.Ю. Шведова. Толковый словарь русского языка
КОЕ... и (разг.) КОЙ-..., приставка. Образует местоименные слова со знач.:
1) неопределенности, напр. кое-кто, кое-какой, кое-где, кое-откуда;
2) низкой оценки качества, напр. кое-как.
ВСЕ, первая часть сложных слов со знач.;
1) охватывающий всех, распространяющийся на всех, на все, на весь предмет, напр. всевидящий, всезнающий, всеведение, всероссийский, всеславянский, всесокрушающий, всепреодолевающий, всепрощающий, всепобеждающий;
2) постоянно, напр. всевозрастающий;
3) самой высокой степени признака, напр. всецело, всесильный, всевластие, Всевышний, всенепременный (устар.).
Итак, приставка кое- имеет общий смысл неопределенности/избирательности, а "первая часть сложных слов" все-, то есть практически приставка, произошедшая от местоимения весь, также имеет всем понятный смысл. Наречие всегда обычно понимается как все + года (ср. иногда ~ иного года, тогда ~ того года, когда ~ коего года). Наречие везде (др-рус. вьсьжде - кругом, повсюду, от местоимения вьсь - весь). Фасмер? Он не возражает :
ВЕЗДЕ
др.-русск., ст.-слав. вьсьде (Супр.), сербохорв.
свагде, словен. vsigde, полаб. visde. Связано с
др.-русск., ст.-слав. вьсь + наречный суф. -де;
ср. где. Ср. также диал. новообразование
всегде (севск.) под влиянием всегда...
Существует окказионализм коегдешний - пишется слитно. Можно предположить возникновение слова когде (когда + где). "Когде мы встретимся?" Что же из этого следует? Изменения в орфографии были, есть и будут, но всему свое время!