Это происходит потому, что правила склонения фамилий – один из наиболее сложных разделов русской грамматики (главным образом ввиду разветвленности самой системы имен и фамилий). Этим правилам уделяют недостаточно времени в школе на уроках русского языка, хотя вопрос «Склоняется ли моя фамилия и как?» встает практически перед каждым носителем фамилии, не оканчивающейся на -ов(а) или -ин(а). Отсюда столько вопросов на эту тему (в том числе в нашем «Справочном бюро» – ежедневно) и столько ошибок. Не застрахованы от ошибок и работники официальных органов, учреждений образования и др. организаций, выдающих документы гражданам.
Тем не менее, если Вы откроете любой нормативный грамматический справочник, Вы прочитаете правило: склоняются мужские и женские фамилии, оканчивающиеся на -а, -я, которым предшествует согласный (кроме французских с ударением на последнем слоге типа Дюма, Золя). Фамилия Воевода – не исключение.
Вы правы. Женские имена на -ия, в которых я безударное, имеют в дательном падеже окончание И: Марии, Лилии, Виктории. Однако личные имена восточного и иного происхождения, оканчивающиеся на ударное я, имеют в дательном падеже окончание Е: Зульфия – Зульфие, Алия – Алие. Это правило изложено в полном академическом справочнике «Правила русской орфографии и пунктуации» (М., 2006), «Словаре русских личных имен» А. В. Суперанской (М., 2004) и мн. др. источниках.
Грамматически верно: аттестат выдан муниципальным общеобразовательным учреждением средней общеобразовательной школой № 1. Или так (как принято в канцелярской речи): аттестат выдан муниципальным общеобразовательным учреждением "Средняя общеобразовательная школа № 1".
Правильно: аттестат о среднем образовании, аттестат зрелости (устар.).
О мужской фамилии: аттестат выдан Соловею (предпочтительно) и Соловью (допустимо). При выборе варианта желательно проконсультироваться с обладателем фамилии.
Если Вас интересует склонение фамилии, то правильно: кому? Салию Виталию. Женская фамилия не склоняется: кому? Салий Татьяне. Подробно см. в Письмовнике.
Фамилия Рахматиллозода склоняется: выдан Рахматиллозоде.
Имена и фамилии, оканчивающиеся на -е, -о, не склоняются. Правильно: аттестат выдан Муйибулло Рахматиллозоде.
Фамилия Бакерия склоняется. Правильно: аттестат выдан Бакерии.