hi,
bin zwar kein fachmann, aber ich hab mir mal sagen lassen, daß unter linux das relaying grundsätzlich gesperrt ist, und das man es auch nicht deaktivieren kann (von wegen spam schutz und so)
ein mitarbeiter eines isp´s hatte mir mal den tip gegeben, mir eine alte version von sendmail zu besorgen, die dieses "relaying denied" noch nicht aktiviert hatten.
vielleicht kannst du damit etwas anfangen.