Relay access denied

issue: i am experiencing mail flow issues between my domain & one of my client(remote domain)

as part of investigation, i have connected to client remote domain gateway mail exchanger via telnet (using port 25) and tried to send an email to my domain mailbox. it given me the RELAY ACCESS DENIED error as below.

220 remotedomain.com AMEX SMTP Relay
ehlo city.com
250-some remotedomain.com
250-PIPELINING
250-SIZE 10485760
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250 8BITMIME
mail from:remoteuserid@remotedomain.com
250 2.1.0 Ok
rcpt to:mydomainid@mydomain.com
554 5.7.1 : Relay access denied
rcpt to:mypersonelid@gmail.com
554 5.7.1 : Relay access denied

i tried to send an email to my gmail id.. no luck got same error.

can anybody explain me the issue& provide me the solution.

Thanks in advance.