Запятая не нужна. Обороты с предлогом начиная с (чего-либо) не выделяются запятыми, если предлог в буквальном смысле указывает на время, дату начала чего-либо (при этом слово «начиная» обычно можно опустить).
Числительные два, три, четыре (а также составные числительные, оканчивающиеся на два, три, четыре, например двадцать два) в именительном падеже сочетаются с существительным в форме родительного падежа и единственного числа, например: двадцать два стола, тридцать три несчастья, пятьдесят четыре человека. Числительные пять, шесть, семь, восемь, девять и т. д. и составные числительные, оканчивающиеся на пять, шесть, семь, восемь и т. д., согласуются с существительным, стоящим в форме родительного падежа множественного числа, например: сорок восемь преступников. Однако в косвенных падежах согласование выравнивается: р. п. – двух столов, пяти столов, д. п. – двум столам, пяти столам.
Такая разница в согласовании числительных связана с историей русского языка. Названия чисел 5–9 были существительными женского рода и склонялись как, например, слово кость. Будучи существительными, эти названия управляли родительным падежом существительных, употреблявшихся, разумеется, в форме множественного числа. Отсюда такие сочетания, как пять коров, шесть столов (ср. сочетания с существительными: ножки столов, копыта коров) и т. п.
Сложнее обстояло дело с названиями чисел 2-4, которые были счетными прилагательными и согласовывались в роде, числе и падеже с существительными: три столы, четыре стены, три камене (ср.: красивые столы, высокие стены). При этом название числа 2 согласовывалось с существительными в особой форме двойственного числа (не единственного и не множественного; такая форма применялась для обозначения двух предметов): две стене, два стола, два ножа (не два столы, два ножи). К XVI веку в русском языке происходит разрушение категории двойственного числа, и формы типа два стола начинают восприниматься как родительный падеж единственного числа. Особая соотнесенность чисел 2, 3 и 4 (возможно, и грамматическая принадлежность к одному классу слов) повлияла на выравнивание форм словоизменения всех трех числовых наименований.
Средне... – (первая часть сложных слов) составляющий среднюю величину для какого-л. отрезка времени: среднесуточный, среднегодовой (средний по каким-л. показателям за год) и т. д.
Стомиллионный (в сочетании с существительным народ) — это прилагательное. Верно, что оно мотивировано составным количественным числительным, но обозначает оно признак предмета и, самое главное, не является порядковым: оно служит не для обозначения порядкового номера предмета при счете (такого количества народов на Земле нет и быть не может, как бы мы ни подсчитывали), а для выражения идеи огромности одного конкретного народа.
Если же мы говорим что-нибудь вроде Я тебе уже стомиллионный раз повторяю! — в этом случае перед нами порядковое числительное, потому подразумевается (с преувеличением, конечно), что до этого повторял(а) уже 99 999 999 раз.
В словосочетании семидесятый год перед нами порядковое числительное, оно называет порядковый номер предмета при счете (в данном случае — при счете лет). Если мы говорим В семидесятые ты еще под стол пешком ходил, то используем это слово в расширительном значении, но оно сохраняет признаки порядкового числительного.
Что касается «Русской грамматики», то нужно иметь в виду, что ее авторы ставили перед собой задачу дать максимально последовательное описание грамматического строя русского языка, что привело их к ряду решений, непривычных для человека, окончившего среднюю школу. В частности, они отказали словам, которые традиционная грамматика считала порядковыми числительными, в принадлежности к числительным — на том основании, что у этих слов нет абсолютно никаких морфологических отличий от, например, относительных прилагательных: они точно так же изменяются по родам, числам и падежам, причем имеют точно ту же систему окончаний, что и обычные прилагательные. (А вот количественные числительные имеют целый ряд морфологических отличий от существительных.) Поэтому в «РГ» отсутствует понятие порядкового числительного, зато появилось понятие порядкового прилагательного.
В формулировке вопроса непонятно, почему автор говорит о поэтах и «стихотворном материале». Разве эти слова функционируют только в поэтической речи?
В первую очередь следует отметить, что название праздника – Новый год, а не Новый 2009 год. Поэтому верно: Поздравляем с Новым годом!
Если все же рассуждать о правописании приведенного в вопросе сочетания (а рассуждать нужно, поскольку это сочетание в преддверии Нового года встречается все чаще и чаще), то можно отметить несколько интересных орфографических и пунктуационных особенностей.
Во-первых, поскольку 2009 год (пусть даже и новый) – это не название праздника (этой фразой мы поздравляем не столько с праздником Новый год, который отмечается ежегодно 1 января, сколько с наступлением собственно очередного года), слово новый здесь следует писать со строчной. Ср.: наступил Новый год (праздник), но: начался новый год.
Во-вторых, слова две тысячи девятый выступают в роли пояснительного определения к слову новый, и поэтому между этими определениями требуется запятая: новый, 2009 год. (Ср. пример из справочника Д. Э. Розенталя «Пунктуация»: Вскоре мы вступим в новое, XXI столетие). Если запятую не поставить, то получится весьма странное по смыслу сочетание «новый (т. е. еще один) две тысячи девятый год», как будто в истории человечества такой год уже был и раньше.
Итак, если поздравлять с праздником, то поздравлять нужно с Новым годом. Если же поздравлять с наступлением очередного года, то поздравлять с новым, 2009 годом.
А как быть с наступающим праздником? О нем мы напишем: С наступающим Новым годом!
Почему же написание рассматриваемой фразы вызывает столько вопросов? Каким образом в поздравление с Новым годом (с праздником, а не с годом календарным) «вкрались» цифры? Можем предположить, что это произошло благодаря «открыточно-оформительской» культуре: в открытке порядковое числительное, обозначающее «номер» года, могло кочевать с места на место (номер года писали, например, на елочных украшениях, нарисованных на открытке), и в конце концов это числительное заняло свое место в названии праздника, между прилагательным Новый и существительным год. Точно так же цифры являются непременным атрибутом новогоднего оформления улиц, функционируя в особой, внетекстовой, внесинтаксической, среде. Именно то обстоятельство, что числительное изначально могло функционировать не как часть текста, а как декоративный элемент, – именно оно повлияло на сложившиеся (противоречащие пунктуационным законам!) традиции оформления данной фразы.
