I'm surprised no one has pinged you for top posting yet. Please post your
reply below everyone elses - it makes for reading the list so much easier.
Anyway, your logs point to a DNS issue, not graylisting. Some of the sites
might be doing it but it really looks like your mail server just can't resolve
anything and as a result, can't verify recipients and can't accept mail! You
also can't find a really easy one like gmail.com.
You have one successful mail so I would say it's an intermittent problem with
DNS so it's going to be really fun to find too.