Email relaying issue?

[Coco]

I setup an email server about a year ago with help from people here and everything was fine untill this morning when I started to recieve this.

----- Transcript of session follows -----
... while talking to smtp.telus.net:
>>> DATA
<<< 554 <name1@gmail.com>: name1@gmail.com rejected: Relay access denied
554 5.0.0 Service unavailable

Final-Recipient: RFC822; name2@mydomain.com
X-Actual-Recipient: RFC822; name1@gmail.com
Action: failed
Status: 5.0.0
Remote-MTA: DNS; smtp.telus.net
Diagnostic-Code: SMTP; 554 <name1@gmail.com>: name1@gmail.com rejected: Relay access denied
Last-Attempt-Date: Wed, 17 May 2006 10:53:39 -0600

I've kinda resolved the issue for now by simply not relaying messages through smtp.telus.net anymore. However, doing this also means some servers will think my emails are spam, which is why I was relaying through them in the first place.

I've tried to research this error as much as possible and as far as I can tell it's because I'm suppost to be logging into smtp.telus.net but I'm not sure how to configure it to do that? Does that even make sense? If not is there some other way I can make my emails always go through without them being detected as spam?

PS: This server is run off a telus business line, so I am actually allowed to run a mail server as far as the ISP is concerned. Also, I edited the email address, but left the rest of the error the same.

Thanks in advance for any help you can offer.

[Mboo]

I had faced this problem before and probably it is related to IP address issues and DNS.
So, has your IP address changed since that time? are you using static or dynamic IP? Are you using your own DNS server or your ISP DNS servers?

To check all these are important. Relaying through your IP address can make difference.

[Coco]

My IP has never changed. I'm using a static IP and I'm using my ISP's DNS servers.