As others have said, you need to check the logs to find out what QMail is seeing when it tries to deliver e-mail to that domain.
Additionally, you may wish to try to manually send an e-mail from the QMail box to the remote mail server. To do that, perform the following steps:
Find the actual mail server handling mail for example.com by running the following command from a command prompt (replacing example.com with the domain you are having problems with):
foo@bar$ host -t mx example.com
In response to that query, you'll get one or more responses of the form:
example.com mail is handled by 20 mail.example.com.
example.com mail is handled by 30 mail.example.com.
example.com mail is handled by 10 mail.example.com.
These are the mail servers designated for this domain. You'll want to take the hostname with the lowest number to work with in our next step. (If you get back the answer that example.com has no MX record, then just use the original hostname/domain name as your mail destination for below.)
Next we'll use telnet to manually connect to the mail server and attempt to send an e-mail. In the example below, I will indent the response lines the server is sending back with a few extra spaces to help clarify what you should type, and what you might get back (note, there will be some slight variation depending on mail server software).
foo@bar$ telnet mail.example.com 25
Connected to mail.example.com.
Escape character is '^]'.
MAIL FROM: <email@example.com>
250 2.1.0 Ok
RCPT TO: <firstname.lastname@example.org>
250 2.1.5 Ok
354 End data with <CR><LF>.<CR><LF>
From: Foo <email@example.com>
To: Bar <firstname.lastname@example.org>
Subject: Foo -> Bar Test
This is a test e-mail from Foo to Bar.
250 2.0.0 Ok: queued as BE0D91F459
221 2.0.0 Bye
Connection closed by foreign host.
Note at the end there it gave a response of
Ok. That line is signifying that the e-mail was accepted for delivery. If it had given a different response code, that would help indicate what the problem might be. The mail server might also offer additional details on the problem, as well.
Don't forget to replace e-mail addresses and hostnames with the valid and appropriate entries for your testing.