Hola
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...)
