Корректно: Поздравляю с прошедшим праздником Успения Пресвятой Богородицы и праздником Перенесения из Едессы в Константинополь Нерукотворенного Образа Господа нашего Иисуса Христа (если прошедшим является только первый праздник) или Поздравляю с прошедшими праздниками Успения Пресвятой Богородицы и Перенесения из Едессы в Константинополь Нерукотворенного Образа Господа нашего Иисуса Христа (если прошедшими являются оба праздника).

Правила выбора формы определения при существительных — однородных членах подробно изложены в § 195 пособия Д. Э. Розенталя, Е. В. Джанджаковой и Н. П. Кабановой «Справочник по правописанию, произношению, литературному редактированию».

Правильно: Скандал вспыхнул после футбольного матча между одесским "Черноморцем" и львовскими "Карпатами", (после матча какого?) прошедшего в Одессе. 

Более корректен вариант с наступившим днем рождения. 

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

Вы совершенно правы.