Qmail does not send e-mail

The qmail queue on my dedicated server is getting larger constantly. For the last 4 days or so, no e-mail is being delivered to the target server. The users are able to accomplish the send/reseive task on the mail reader without any problems. There does not seem to exist any problems about the incoming mail, either. They are delivered to the local mailboxes. But when people try to send e-mail from my server, it stays in the queue. The e-mails are either not delivered at all or delivered with one or two days delay. There are about 11000 emails in the queue. I have been following the queue since there were 2000 e-mails. Every other few hours, the queue has a few hundred more e-mails. I checked if any of the mailboxes exceeded quota. But none of them has this problem. So it is not about one mailbox making qmail slow down. When I check the queue, I founnd out that more than 40% of the e-mails are something about the postmaster. A sample data is as follows;

11 Jun 2006 23:20:30 GMT #9192916 3627 <#@[]>
remote postmaster@server.name.dom

I would like to have the server become capable of send e-mails without problems ASAP. Any ideas about what the next step might be in order to get closer to the solution?

Finally I do have an error message

The emails sent returns the following error message. I read some information which says it is about the 512 bytes limit of qmail about accepting cname lookups but still I don't know what I can do.

The error message:
CNAME lookup failed temporarily. (#4.4.3)
I'm not going to try again; this message has been in the queue too long.

Check if DNS is working on your server. Try ping yahoo.com and see if server is able to resolve domain to IP.

how to check the dns is working on my server?ping for which server to resolve domain

Could you check whether your servers /etc/resolv.conf is readable to 'others' ?