Segundo o Dicionário da Academia, a expressão «fazer votos» rege as preposições
– de: «(fazer) votos de boas festas»;
– para: «fazer votos para que tudo corra bem».
– por: sem exemplo
Quanto aos exemplos que apresenta, considero ambos bem formados. Não posso dizer-lhe a razão pela qual o primeiro, que repito como (1), estando correcto, lhe soa mal, pois esse facto poderá ter que ver com a sua própria sensibilidade linguística.

(1) Faço votos de que as minhas acções vão ao encontro das vossas expectativas.

Posso apenas dizer-lhe que essa frase inclui dois “pontos quentes” da língua portuguesa.
Um deles é a sequência «de que», que está em reanálise, ou seja, em transformação, pelo menos em alguns casos. Com efeito, regista-se com muita frequência a queda do de em sequências deste tipo.

Outro é a expressão «ao encontro de», muito bem utilizada, mas que muitos teimam em substituir, nesse contexto, por “de encontro a”…

Quanto a ano novo, se se referir àquela data, comemorada no dia 1 de Janeiro, e que é conhecida por esse nome, então justifica-se tanto a maiúscula como em Natal, Carnaval ou Páscoa… se se refere a ano novo, por contraste com ano velho, sem pretender individualizar nenhum deles, então não se justifica, sendo, porém, o uso da maiúscula aceitável quando se pretende individualizar o conceito.