[exim] No route to host - but i can ping the host

Hi All

I am using EXIM4 and am having issues with exim not sending mail to
well known host like gmail, hotmail, yahoo and others, taking upto
6hrs or more to deliver a message.

I looked in my logs and i noted that the error it gives for this is

2008-10-30 08:43:01 1KvABY-0002XP-Qz g.mx.mail.yahoo.com
[206.190.53.191] Connection timed out
2008-10-30 08:43:04 1KvABY-0002XP-Qz e.mx.mail.yahoo.com [216.39.53.1]
No route to host
2008-10-30 08:43:07 1KvABY-0002XP-Qz f.mx.mail.yahoo.com
[209.191.88.247] No route to host
2008-10-30 08:43:28 1KvABY-0002XP-Qz f.mx.mail.yahoo.com
[68.142.202.247] No route to host
2008-10-30 08:43:31 1KvABY-0002XP-Qz a.mx.mail.yahoo.com
[209.191.118.103] No route to host
2008-10-30 08:46:40 1KvABY-0002XP-Qz d.mx.mail.yahoo.com [66.196.82.7]
Connection timed out
2008-10-30 08:46:43 1KvABY-0002XP-Qz c.mx.mail.yahoo.com [216.39.53.3]
No route to host
2008-10-30 08:47:04 1KvABY-0002XP-Qz c.mx.mail.yahoo.com [216.39.53.2]
No route to host
2008-10-30 08:47:13 1KvABY-0002XP-Qz b.mx.mail.yahoo.com
[66.196.97.250] No route to host
2008-10-30 08:47:13 1KvABY-0002XP-Qz == xxxxxxxxx@??? R=dnslookup
T=remote_smtp defer (113): No route to host

2008-10-30 08:47:20 1KvA60-0002X2-Jr mx03.realtime.zm [196.46.124.17]
No route to host
2008-10-30 08:48:05 1KvA60-0002X2-Jr mx02.realtime.zm [196.46.125.3]
No route to host

2008-10-30 08:50:00 1KvRBR-0003p1-LK mx2.hotmail.com [65.54.245.40] No
route to host
2008-10-30 08:50:03 1KvRBR-0003p1-LK mx2.hotmail.com [65.54.244.40] No
route to host
2008-10-30 08:50:06 1KvRBR-0003p1-LK mx2.hotmail.com [65.54.244.168]
No route to host
2008-10-30 08:50:09 1KvRBR-0003p1-LK mx1.hotmail.com [65.54.245.8] No
route to host
2008-10-30 08:50:12 1KvRBR-0003p1-LK mx1.hotmail.com [65.54.244.8] No
route to host
2008-10-30 08:50:12 1KvRBR-0003p1-LK == xxxxxxxx.xxxxxxxx@???
R=dnslookup T=remote_smtp defer (113): No route to host

can anyone help sort this out because i can ping theses host but exim
cant send mail to them

Thanks