Does this happen on all domains except for yahoo, hotmail and gmail or only on specific domains?
Does it happen only when you send large amount of email at once (e.g. some marketing mailing) or even when sending message to single recipient? I had similar issue during email marketing campaigns and it was related to Windows DNS and firewall (Netscreen). I will describe it in more detail if your issue shows up in similar situations.
Do you have extended logging enabled in Exchange? If not enable it and check how the SMTP transmission looks for this recipient.