Abre una terminal en un equipo de tu oficina y escribe:
telnet tu_servidor_smtp puerto_que_tengas_asignado
por ejemplo, si tu servidor es smtp.miservidor.net y el puerto el 25 (el por defecto)
telnet smtp.miservidor.net 25
si está bien te tiene que responder con un mensaje que empieza por el número 220
OJO si tienes Windows 7
seguramente tendrás que activar el cliente de telnet.
OJO los puertos tienen que ser los que te dice tu proveedor de correo, no puedes cambiar puertos porque si.
Si no te responde y como dices puedes enviar correo usando otro proveedor de internet a través del movil quiere decir que tu proveedor de internet te está capando el puerto, llamale y les dices que has comprobado que esos puertos están bloqueados desde su servicio, que sois una empresa y que os los tienen que abrir.
Editado
=====
Asumo por supuesto que vosotros no habeis tocado el router que os da salida a intenet claro.