G Day
I am having the same problem as above, the users the mail is being denied relay is for users on the local machine.
I get the following error
check_goodrcptto 901 relaying denied user@domainx.com message denied before queue
but user@domainx.com exists on the local server, and is a valid user as follows ( all details cahnged to protect the innocent

Hi. This is the qmail-send program at yahoo.com.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.
<user@domainx.com>:
XXX.XXX.XXX.XXX does not like recipient.
Remote host said: 550 relaying denied user@domainx.com
Giving up on XXX.XXX.XXX.XXX.
--- Below this line is a copy of the message.