Союз вместе с тем не требует выделения знаками препинания. Союзные сочетания а вместе с тем, но вместе с тем, как правило, соединяют простые предложения в составе сложного и перед ними ставится запятая или другой знак препинания.

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

1. «Правила русской орфографии и пунктуации» 1956 года – это официально действующие в настоящее время правила русского правописания. Официально действующие – но в ряде случаев значительно отстающие от современной практики письма, противоречащие ей, – такой вот парадокс. Написание с прописной буквы слова Бог не соответствует этим правилам, но в той же степени не соответствует им, например, написание с прописной слова Республика в сочетании Французская Республика, ибо согласно правилам 1956 г. слово республика пишется с прописной только «в официальных названиях советских республик и стран народной демократии». Раздел «Прописные буквы» в этом своде правил – пожалуй, наиболее устаревшая часть. В современных словарях и справочниках (некоторые из них приведены в пункте 2) рекомендации свода 1956 года пересмотрены, правила употребления прописных букв сформулированы заново, сейчас следует руководствоваться именно этими правилами.

2. См.: Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2007; В. В. Лопатин, И. В. Нечаева, Л. К. Чельцова. Прописная или строчная? Орфографический словарь. М., 2007;  Мильчин А. Э., Чельцова Л. К. Справочник издателя и автора. М., 2003.

3. В политеистических религиях, действительно, существуют тысячи богов, поэтому, если речь идет об одном из верховных существ в политеистических религиях,  бог – нарицательное существительное (и пишется со строчной). Однако монотеистические религии основаны как раз на том принципе, что существует только один бог, поэтому в значении 'единое верховное существо в монотеистических религиях' слово Бог сближается с именем собственным, на этом и основана рекомендация писать это слово с прописной.

4. См. пункт 2. В этих изданиях употребляется именно слово «рекомендуется» (поэтому и мы так пишем). По поводу того, как оценивается написание бог / Бог в школьных сочинениях и диктантах, ничего не можем сказать (не знаем); вероятно, правильнее всего было бы не считать ошибкой ни то, ни другое написание, но рассказать ученикам о данной орфографической проблеме, о том, как она решается сейчас, какие рекомендации приведены в современных справочниках по правописанию.

Выбор формы причастия зависит от смысловых отношений между словами. Определенного грамматического правила для таких случаев нет.

Так, в первом предложении возможны варианты согласования. Причастие будет согласовываться со словом вид, если графика выделяется среди других видов искусства, которые существуют с конца 15 века: Одним из самостоятельных видов искусства, существующих с конца 15 века, является графика. Если же необходимо подчеркнуть, что именно графика существует с конца 15 века, то правильно: Одним из самостоятельных видов искусства, существующим с конца 15 века, является графика.

Во втором предложении также возможны варианты: Школьники нашего села охотно помогали группе археологов, приехавшей из Новгорода и Школьники нашего села охотно помогали группе археологов, приехавших из Новгорода.

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

Теперь обратимся к слову заревать. В середине ХХ в., когда формировался орфографический минимум для школы, это слово не было включено в правила и учебники, адресованные детям и учителям. Вероятнее всего, причина в том, что это слово крайне редкое. В основном подкорпусе «Национального корпуса русского языка» сейчас находится лишь три документа с вариантом заревать, и восемь с вариантом зоревать. В большинстве толковых словарей, в том числе в «Большом академическом словаре русского языка», который начал издаваться в 2004 г., ни в одном из вариантов написания глагол не фиксируется. 

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

Специалисты, составляющие задания для ЕГЭ, осведомлены о многих проблемах современной орфографии и стараются проблемные слова типа заревать в материалы не включать. 

Согласны с Вами, логичнее рассматривать сказуемое как составное именное.