there have been reports where psexesvc.exe had not been removed on the target machine (folder: %windir%). If such a leftover psexesvc.exe is older than the psexec.exe which tries to use it, this will lead to trouble.
So checking whether an old psexesvc.exe still exists inside %windir% (ADMIN$) on a failing target machines may be worth a try.
other user had the problem and said
" there is another psexesvc.exe at c:\windows of different size and it may be older or newer version. I just "sc.exe delete psexesvc" to get rid of that one and rerun psexec to the host and it solved my problem."