It appears that there is an 18 character limit on the processname parameter, and so with the very long process it was simply rejecting it.
The solution to kill MyVeryLongProcessName.exe is therefore:
c:\> tskill MyVeryLongProcessN
Too many / few characters in the tskill parameter and it will just return a process not found error.