When STSADM executes, it tries to load strong named assemblies which need to be verified against an authentication provider. When your client has bad or no network access, it waits for a timeout before continuing, which makes the stsadm command very slow.
To pass by this process, edit your machine.config and add:
<configuration>
<runtime>
<generatePublisherEvidence enabled=”false”/>
</runtime>
</configuration>
This should do the trick.