Bizarre Exchange issue; cannot send to external addresses, from all but ONE user
Try creating a new smtp sendmail connector, make sure namespace is * and its internet based delivery. see if you can right click disable for the existing one after the new one is setup and then try delivery.
I'd first suggest trying to send from OWA if the delivery works then at least this is a for sure way to bypass and client side issues and narrow it down to a server side problem.