Hola
Se problema puede darse si el usuario en cuestión no tiene asociada la dirección de correo concreta que se está poniendo en el programa de correo.
Si entras con el usuario administrador a https://login.microsoftonline.com puedes verificar si tienes el dominio asociado y esa dirección (de tu dominio propio) asignada al usuario que te da problemas. Si el dominio está asociado y está verificado, el siguiente paso es ver que ese usuario tiene todas las direcciones de correo autorizadas.
Para verlo, entrando como administrador, en la página de bienvenida a la derecha aparece el menú "dominios", tras pulsarlo, sale la lista de dominios y subdominios de tu organización: siempre saldrá el miempresa.e.telefonica.net (o e.movistar.es si es más reciente), un te######### y los dominios propios que se tenían contratados en Escritorio.
Si tu dominio está ahí y su estado es "Activo" significa que está verificado en O365 y que puedes utilizarlo para enviar/recibir. A continuación, ve a "Usuarios y grupos" en el menú de la derecha, pulsa sobre el nombre del usuario (buzón), pulsa el menú "Más" de la derecha y en el enlace "Editar propiedades de Exchange". Aparece la ficha de configuración del buzón. Pulsa en el menú "Dirección de correo electrónico" y te saldrá la lista completa de direcciones con las que el usuario puede enviar y recibir. Ahí debería estar la dirección usuario@midominio.es que ahora no puedes utilizar. Si no está, debes añadirla, pero sólo podrás si el dominio está añadido a Office 365 y verificado como te comentaba antes. Fíjate que aparece en la tabla una columna "Tipo" con SMTP y smtp, la que aparece en mayúsculas será la dirección de remitente que figurará cuando envíes desde OWA (webmail).
Hay que tener en cuenta que si te llevaste el dominio fuera de Escritorio a otro registrador o pediste el authcode, en la actualización Movistar ya no estaba autorizada a hacer cambios sobre tu dominio y no ha podido asociarse al correo actualizado a Office 365, pero no es insalvable pues se puede asociar el dominio estando fuera (se indica en http://office.microsoft.com/en-us/office365-suite-help/add-your-domain-to-office-365-HA102818656.asp...)
