Vossa Excelência é uma forma de tratamento pronominal que existe na Língua Portuguesa desde o século XV. Até então, as formas de tratamento eram tu, para o tratamento informal no singular, e vós, também 2.ª pessoa do singular, para o tratamento formal. No plural a forma era sempre vós, 2.ª pessoa. Hoje, temos para o singular a forma tu, informal; você, A tia, o meu amigo, para o tratamento formal e o Senhor, a Senhora, o Senhor Doutor, o Senhor Director, o Senhor Ministro, o Senhor Presidente, Vossa Senhoria, Vossa Excelência, Vossa Reverência, (...), como forma de tratamento de cerimónia.
A diferença entre Vossa e Sua está, quanto a mim, relacionada com o desaparecimento do pronome de cortesia para o singular, vós. Este pronome era, inicialmente, aplicado com a forma verbal flexionada no plural. Com a evolução própria da Língua Portuguesa, a utilização desta forma passou a ser feita conjugando o verbo na 2.ª pessoa do singular, tal como tu. Penso que o pronome possessivo Vossa era usado referindo-se a Vós, forma de cortesia da época, com a conjugação no plural e, dado que esta forma deixou de existir com este uso, passou a ser aplicado o pronome possessivo correspondente à 2.ª pessoa do singular de tratamento formal e cerimonioso Você, o Senhor, a Senhora. É de salientar que as formas Vossa Excelência e Sua Excelência não se substituem, coexistem, pois, dada a ambiguidade do pronome sua, que tanto pode referir-se a si (ex.: «Aqui a sua mala, D. Maria».), como a ele ou a ela (ex.: «Maria esperou que a sua tristeza passasse»), o possessivo aplica-se apenas nesta última referência).
Quando se refere ao Presidente da República, deve fazê-lo usando a forma o Senhor (por extenso e com maiúscula). Assim, eu escrevi ao Senhor Presidente da República. É, contudo, frequente ouvir vai agora falar Sua Excelência o Presidente da República, em que Sua Excelência é uma forma de cerimónia indirecta, por oposição a Vossa Excelência que, quando aplicada, é como forma de tratamento directo, como é exemplo Escrevo a Vossa Excelência a solicitar...

N.E. – Estas são as regras gerais do tratamento de cerimónia ou protocolar, que não correspondem exactamente ao que já faz regra na escrita mais informal, como é o caso dos jornais. Onde, por exemplo, senhor, director, ministro, presidente (excepção: Presidente da República), etc., se grafam em minúsculas.