Правильно именно с не во всех приведенных Вами примерах: Нет такого уголка в наших степях, куда бы не проникли машины. И нет уголка, куда бы не проникла его мысль. Нет ни одного общества, где бы не существовало гетеротопий. Следует различать в придаточных предложениях сочетания кто бы ни, куда бы ни и т. д., в составе которых имеется частица ни, примыкающая к относительному слову, и сочетания кто бы не, где бы не, куда бы не и т. д., в составе которых имеется частица не, относящаяся к сказуемому.

За тридевять земель – очень далеко. Этот фразеологизм фольклорного происхождения. Слово тридевять представляет собой сложение двух числительных: три и девять. Оно восходит к тому времени, когда на Руси наряду с десятеричной системой исчисления существовала и девятеричная (в этой системе тридевять обозначало 27).

Выражение за тридевять земель обычно для русских сказок в форме троекратного повтора: за тридевять земель, в тридевятом царстве, в тридесятом государстве. В сказках это выражение отдаляется от точного числительного и означает просто «очень далеко». Это современное употребление и значение сложилось не сразу, а примерно на рубеже XVIII и XIX вв.

Инфинитива болить нет и никогда не существовало. В современном русском языке есть два глагола болеть. Первый имеет значение ‘быть больным’ и спрягается как глагол иметь: болею, болеешь, болеет и т. д. Второй имеет значение ‘вызывать ощущение боли’, спрягается как глагол гореть, но употребляется почти всегда в формах 3-го лица: голова болит, ноги болят (об употреблении в форме других лиц см. ответ на вопрос № 324535). В древности в обоих значениях употреблялся именно этот, второй глагол (болѣти — болю, болиши, болить и т. д.). Две парадигмы глагола болеть фиксируются с XVIII века.

Если на стыке основ образуется удвоенная согласная, то это удвоение должно сохраняться, чтобы, как писал М. В. Ломоносов, не закрывать следы произвождения и сложения речений. Ясность структуры слова особенно важна для терминов. Соединение основ фальш- и шток- должно образовывать слово фальшшток. Написание фальшток может быть воспринято как соединение основ фальш- и ток-. Конечно, удвоение ш нехарактерно для русского языка, поэтому у пишущего может возникнуть желание разделить части дефисом. Если бы существовала устойчивая традиция дефисного написания, то слово могло бы претендовать на включение в словарь с дефисом, как исключения из правила. Но в отсутствие такой традиции предпочтительно написание по правилу. 

Разное значение этих глаголов определяется разным значением приставок пре- и при-: пре- вносит в слово значение крайней степени проявления чего-либо, а при- — значение некоторой незначительной степени проявления чего-либо. Поэтому преуменьшить означает  "представить что-л. в меньших по сравнению с действительностью размерах", а приуменьшить — "немного уменьшить". На практике разграничить эти два написания может быть затруднительно, поэтому решение о написании е или и в приставке остается за автором текста. Сравнительно недавно существовала еще одна орфографическая пара такого типа: преумножить и приумножить. Однако несколько лет назад было принято единое написание с буквой и в приставке — приумножить. 

Это слово существовало в прошлом. Оно известно со времен древнерусского языка и встречается вплоть до конца XIX — начала XX века, ср., например: Всё Евангелие наполнено и прямыми, и приточными указаниями на прощение… (Л. Н. Толстой, 1887). В «Толковом словаре русского языка» под ред. Д. Н. Ушакова (т. 3, 1939, стлб. 867) это прилагательное приведено еще без всяких помет, но уже в «Словаре современного русского литературного языка» (т. 11, 1961, стлб. 812) при нем значится помета «устар.». Прилагательное же притчевый очень молодое: в Национальном корпусе русского языка его самая ранняя фиксация приходится на 1970-е годы.

Никаких достоверных свидетельств того, что слово нос в древности имело значение ‘бирка с зарубками’, не существует. Такое употребление не известно ни в древнерусских и старорусских текстах, ни в диалектах. Указанная в вопросе версия о происхождении фразеологизма, скорее всего, ошибочна, хотя и растиражирована. Слово нос в данном выражении, видимо, следует понимать в его первом, анатомическом значении (см. Мокиенко В. М. Зарубить на носу // Русская речь. 1983. № 6. С. 91–96). Если всё же предполагать, что слово нос ‘бирка, дощечка’ существовало, в таком случае его следует сближать с глаголом носить и в акцентологическом отношении сопоставлять со словом воз (носить — нос, возить — воз). Ударение в формах слова воз может служить ориентиром: возы́, возо́в, воза́м, воза́ми, воза́х.

Слова ёлка и ёж можно было записать как *йолка и *йож, чтобы написанное читалось так же. То есть теоретически можно было бы отказаться от букв е, ё, ю, я в начале слова, заменив их сочетаниями йэ, йо, йу, йа. Вопрос: а зачем? Ведь буквы е, ё, ю, я (так называемые йотированные) выполняют две функции: в одних позициях (мел, мёл, люк, мял) указывают на мягкость предшествующего согласного (а если бы этих букв не существовало, пришлось бы придумывать отдельные буквы для обозначения мягких согласных, что весьма неэкономно), в других же обозначают сочетания [йэ], [йо], [йу], [йа].

В случаях типа йогурт, йод, майор, Нью-Йорк и т. п. написание йо указывает на иноязычное происхождение этих слов и, так сказать, намекает на их буквенное оформление в языке-источнике.