PsExec (v2.11) can take up to a minute to invoke a process, either locally or remotely.
I'm using the following command line:
psexec.exe -u domain\username -p mypassword -accepteula -d -h \\machinename C:\path\to\myapp.exe
I have the firewall disabled on all machines.
What else can I look at?
UPDATE: I used procmon to highlight the delay: