Could it be that it is not a network issue but a timeout issue, so SQL reports an error even though the SP is still running?

You can run a continuous ping while the job is running to see if there are any drops in connectivity while the job is running. You could also run a Network Monitor trace and see if there is anything that a Network Admin can identify as a networking issue.