Problemas con configuración de EMAIL

Buenas!
Hace tiempo compre un dominio+hosting, con el cual puedo poner varias cuantas de correo xxx@midominio.com por ejemplo.
He creado varios correos, y tengo un problema. y es que configuro todo y recibo los correos, pero a la hora de enviar alguno me dice que el servidor rechaza la conexión. Me han dicho que es problema de telefónica y que tengo que comprarles a ellos los correos...es esto verdad? Es que a mi me da que es problema de configuracion de la red interna del despacho...
¿Tendrás mal configurado el servidor de salida en el programa de correo?
No, lo tengo configurado tal y como me han dicho en la web donde compre el hosting...mi pregunta iba enfocada a ver si puede ser lo de telefonica, que ya me lo han comentado varias personas pero me parece una jugada (aun mas si cabe xd) demasiado sucia hasta viniendo de donde viene...
2 respuestas