Headers in mail() are not accepted by Yahoo and Hotmail

[eluser]Rubiz'[/eluser]
Hello all!

Well, I'm with a mail() problem, it seems the headers of my mail are not appropriated to Yahoo and Hotmail boxes... many times the email even is displayed in client mailbox. Other times, it goes to spam box, never inbox, but I dont get this problem when its Gmail box.

I posted this problem in other forums & communities, nobody got answers about this.

Well, the client has a brand new website in a brand new server host and... no black, gray, or any bad lists...

Anyone could help to solve this problem?