Cannot send to new email users

No one in my company can send emails to a new email address, unless they send us an email first. Once they send us an email we can send to them no problem. has anyone had this problem or know of a way to fix this. thanks.
we are all using outlook 2007.