Here’s a weird one,
When going into OWA from IE 9 or IE 10, using premium mode you can’t send an email to someone who you never have before i.e. you can send emails fine to someone that OWA puts in the autocomplete (NK2 nickname dropdown) but for a brand new address it doesn’t work.
To fix/workaround we did this, applied the below into OWA folder on IIS then restarted IIS, then it seems to work fine.