Ist das vielleicht der SMTP-Server von Deinem normalen Internetprovider? Das hatte ich bei meinem auch, wenn ich nicht über sein Netz komme, dann ist das "Relay denied".
Wenn es so ist, probier einmal die Authentifzierung einzuschalten, bei mir hat das immer geholfen.
Im schlimmsten Fall müßtest Du über einen anderen SMTP-Server gehen.