I have a problem with my postfix email server, I keep getting the following errors in the queue:

F0B09760FE 36747 Thu Apr 26 16:20:25 bounces@icej.org
(Host or domain name not found. Name service error for name=yahoo.com type=MX: Host not found, try again)
john.doe@yahoo.com

F20E21CB492 36715 Thu Apr 26 15:47:48 bounces@icej.org
(delivery temporarily suspended: Host or domain name not found. Name service error for name=hotmail.com type=MX: Host not found, try again)
john.doe@hotmail.com

F353E1CB047 36711 Thu Apr 26 13:53:50 bounces@icej.org
(delivery temporarily suspended: Host or domain name not found. Name service error for name=juno.com type=MX: Host not found, try again)
john.doe@juno.com

F1343766E9 36692 Thu Apr 26 15:07:33 bounces@icej.org
(delivery temporarily suspended: Host or domain name not found. Name service error for name=aol.com type=MX: Host not found, try again)
john.doe@aol.com

I have postfix 2.1.1 running with amavis-new 2.4.5 and its compatriots clamav 0.90.2 and spamassassin 3.1.8. The errors only seem to occur when the non-profit organisation that I work for sends out its daily news service (we have 1000's of emails on our list). I have tried to narrow it down by switching off amavis-new and leaving postfix running by itself. This succeeds in processing the emails in the queue a 100 times quicker, however the error messages still appear.

When I check the mail.warn log I discovered these sorts of entries:
Apr 26 20:56:39 rebekah postfix/smtp[5777]: warning: no MX host for aol.com has a valid A record
Apr 26 20:56:58 rebekah postfix/smtp[5577]: warning: no MX host for hotmail.com has a valid A record
Apr 26 20:57:19 rebekah postfix/smtp[5784]: warning: no MX host for aol.com has a valid A record
Apr 26 20:59:55 rebekah postfix/smtp[5688]: warning: no MX host for peoplepc.com has a valid A record
Apr 26 21:00:35 rebekah postfix/smtp[5737]: warning: no MX host for yahoo.com has a valid A record

And similar entries in my mail.info log:
Apr 26 21:26:27 rebekah postfix/smtp[6888]: 35B671CD0E4: to=<john.doe@hotmail.com>, relay=none, delay=1678, status=deferred (Host or domain name not found. Name service error for name=hotmail.com type=MX: Host not found, try again)
Apr 26 21:26:28 rebekah postfix/smtp[6768]: 4D6011CC9AB: to=<john.doe@telus.net>, relay=none, delay=1543, status=deferred (Host or domain name not found. Name service error for name=telus.net type=MX: Host not found, try again)
Apr 26 21:26:28 rebekah postfix/smtp[6750]: 4972F1CD9A5: to=<john.doe@houston.westerngeco.slb.com>, relay=none, delay=1577, status=deferred (Host or domain name not found. Name service error for name=houston.westerngeco.slb.com type=MX: Host not found, try again)

I have checked my resolv.conf and the ip addresses of my name servers are correctly entered. I have checked the dns forward and reverse lookups for the domain mail.icej.org and everything is set up correctly. I am at my wits end. I have made countless google searches and made countless adjustments, but all to no avail. Any help would be greatly appreciated!

Here is a snapshot of my main.cf file:
mail_owner = postfix
mynetworks = 212.179.112.0/22, 127.0.0.0/8
sendmail_path = /usr/sbin/sendmail
newaliases_path = /usr/bin/newaliases
mailq_path = /usr/bin/mailq
setgid_group = maildrop
canonical_maps = hash:/etc/postfix/canonical
#virtual_maps = hash:/etc/postfix/virtual
relocated_maps = hash:/etc/postfix/relocated
transport_maps = hash:/etc/postfix/transport
deadbeats_destination_concurrency_limit = 50
virtual_alias_domains = grafted.org, grafted.no
virtual_alias_maps = hash:/etc/postfix/virtual
sender_canonical_maps = hash:/etc/postfix/sender_canonical
local_recipient_maps = $alias_maps
masquerade_exceptions = root
masquerade_classes = envelope_sender, header_sender, header_recipient
myhostname = mail.$mydomain
program_directory = /usr/lib/postfix
inet_interfaces = all
masquerade_domains =
mydestination = $myhostname, localhost.$mydomain, $mydomain, $myhostname.il, $mydomain.il
defer_transports =
disable_dns_lookups = no
relayhost =
content_filter = smtp-amavis:[127.0.0.1]:10024
mailbox_command = /usr/bin/procmail
mailbox_transport = cyrus
smtpd_sender_restrictions = hash:/etc/postfix/access
smtpd_client_restrictions =
smtpd_helo_required = no
smtpd_helo_restrictions =
strict_rfc821_envelopes = no
smtpd_recipient_restrictions = permit_sasl_authenticated,permit_mynetworks,reject_unauth_destination
alias_maps = hash:/etc/aliases
mailbox_size_limit = 0
message_size_limit = 10240000
mydomain = icej.org
myorigin = $mydomain
policy_time_limit = 3600

Here is a snapshot of my master.cf file:
smtp inet n - n - - smtpd
smtp-amavis unix - - n - 10 smtp
-o smtp_data_done_timeout=1200
-o smtp_send_xforward_command=yes
-o disable_dns_lookups=yes
deadbeats unix - - n - - smtp
-o smtp_connect_timeout=5
-o smtp_helo_timeout=5
127.0.0.1:10025 inet n - n - - smtpd
-o content_filter=
-o local_recipient_maps=
-o relay_recipient_maps=
-o smtpd_restriction_classes=
-o smtpd_delay_reject=no
-o smtpd_client_restrictions=permit_mynetworks,reject
-o smtpd_helo_restrictions=
-o smtpd_sender_restrictions=
-o smtpd_recipient_restrictions=permit_mynetworks,reject
-o mynetworks=127.0.0.0/8
-o strict_rfc821_envelopes=yes
-o smtpd_error_sleep_time=0
-o smtpd_soft_error_limit=1001
-o smtpd_hard_error_limit=1000

well are you getting mx records for these domains??

After checking the mx for aol.com:

rebekah:/var/log # host -t mx aol.com

I got the following output:

aol.com mail is handled by 15 mailin-03.mx.aol.com.
aol.com mail is handled by 15 mailin-04.mx.aol.com.
aol.com mail is handled by 15 mailin-01.mx.aol.com.
aol.com mail is handled by 15 mailin-02.mx.aol.com.