Hola, Nacho.

>¿A la hora de crear el WSDL debo dejar los nombres de "tempuri" como están o debo cambiarlo por el nombre de mi servidor?

No, lo único que debes cambiar es, en la WSDL:

<soap:address location='http://TuServidor/TuVirtual/TuServicio.WSDL'/>

Cuando lo generas localmente, la URL queda apuntada para tu servidor local (como localhost, o con el nombre de tu PC). Lo que tienes que hacer es poner la URL púplica del servidor.

Aparte de eso, me huele que puedes tener un problema con esas vueltas con los puertos...

Suerte,