Internet msgs to particular destinations stuck in queue

My company is running Exch 5.5 SP4 on W2K SP4. For the last few days we have been unable to send messages to anyone at particular destinations (e.g., so-and-so@destination.net). I can send messages to anyone at these sites using my mail.yahoo.com address without a problem, I just can’t send it from my company! When I look at the “Outbound Msgs Waiting Delivery” queue the messages show “Host unreachable”. Not sure even how to begin troubleshooting this issue. Anyone have any ideas?