Windows-email question:it is linux related

[Slaine <scoetzee@xxxxxxxxxxxx>]

>         No transport provider was available for delivering to this recipient

do you get an access/relaying denied error, if you look at outlook?
add the ip address of each machine into /etc/mail/access (I'm assuming
you're using a
new version of sendmail) and type make in the /etc/mail dir. or the
makemap hash thing.
check your docs

slaine