I was not receiving mails from a particular email address. The MX records checked out fine. The mail server was not in any of the DNSBL list I was subscribed to. There was nothing in the logs that mentioned that there was any emails coming in from the user. However, it did have a lot of relaylocks for the mail servers IP address.
Digging in some more, I found a similar issue discussed at theplanet forum where the issue was caused due to conflict of timeouts and auth packets being dropped instead by the sender mail server, so I adjusted qmail timeout which seemed to push the conversation between the MTAs forward and the emails are now being accepted.
I changed the default timeout from 30 seconds to 15 seconds by editing the /etc/inetd and adding -t15 as below.
smtp stream tcp nowait.1000 root /var/qmail/bin/tcp-env tcp-env -t15 /usr/sbin/rblsmtpd -r bl.spamcop.net -r zen.spamhaus.org /var/qmail/bin/relaylock /var/qmail/bin/qmail-smtpd /var/qmail/bin/smtp_auth /var/qmail/bin/true /var/qmail/bin/cmd5checkpw /var/qmail/bin/true
smtps stream tcp nowait.1000 root /var/qmail/bin/tcp-env tcp-env -t15 /usr/sbin/rblsmtpd -r bl.spamcop.net -r zen.spamhaus.org /var/qmail/bin/relaylock /var/qmail/bin/qmail-smtpd /var/qmail/bin/smtp_auth /var/qmail/bin/true /var/qmail/bin/cmd5checkpw /var/qmail/bin/true