Boas,
Os filtros de spam são muito complicados de lidar porque depende de muitos fatores.
Antes de mais, o email pode estar todo direito, com todos os registos correctos, e ainda assim ser marcado como spam. Existem muitas variantes a ter em conta para classificar isso.
Por exemplo, deve ter em conta também a reputação do IP, outras contas que possam estar a enviar mensagens sobre o mesmo IP, a reputação do próprio domínio, etc.
Um domínio registado recentemente provavelmente vai ter uma reputação mais reduzida ou até um IP que não costume enviar emails ou apenas agora tenha começado a enviar - e portanto, mais probabilidade de ir parar ao Spam. Mas isto é apenas um caso.
Não recebe nenhuma mensagem de erro quando tenta enviar? E apenas acontece com o Yahoo?
Se for esse o caso, pode ser apenas uma questão de reputação do IP ou domínio - e não existe nada a fazer senão enviar emails e pedir para que sejam marcados como legítimos.