Not able to deliver emails to certain users, for certain users in certain machines!!

I have a few users using Outlook Web Access who have problem sending email to certain users from their machines. They get a NDA “The e-mail address could not be found. Perhaps the recipient moved to a different e-mail organization, or there was a mistake in the address. Check the address and try again.”. But the same user is able to send email in a different machine and also other users are able to send from his machine using OWA to the same mail recepient. It seems strange but I dono know why. Can somebody help?