PowerShell remoting from a Windows service

I have a Windows service that regulary runs a PowerShell script on a remote computer via WsManConnectionInfo/RunspaceFactory (following the steps from this article: Remotely Executing Commands in PowerShell using C#):

var connectionInfo = new WSManConnectionInfo(false, server, 5985, "/wsman",
                                             "http://schemas.microsoft.com/powershell/Microsoft.PowerShell",
                                             cred)
                        {
                            OperationTimeout = 4*60*1000,
                            OpenTimeout = 1*60*1000
                        };
using (var runSpace = RunspaceFactory.CreateRunspace(connectionInfo))
{
    runSpace.Open();
    using (var p = runSpace.CreatePipeline())
    {
        p.Commands.AddScript(script);
        var output = p.Invoke();
        ...
    }
}

Now, if I run the Windows service itself with an Administrator account, all is well. But if i run the service with the LocalSystem account, I get the following exception;

System.Management.Automation.Remoting.PSRemotingTransportException:
    Connecting to remote server NOSRVDEV02 failed with the following error message :
        WinRM cannot process the request. The following error with
        errorcode 0x8009030d occurred while using Negotiate authentication:
        A specified logon session does not exist. It may already have been terminated.

    Possible causes are:
        -The user name or password specified are invalid.
        -Kerberos is used when no authentication method and no user name are specified.
        -Kerberos accepts domain user names, but not local user names.
        -The Service Principal Name (SPN) for the remote computer name and port does not exist.
        -The client and remote computers are in different domains and there is no trust between the two domains.

    After checking for the above issues, try the following:
        -Check the Event Viewer for events related to authentication.
        -Change the authentication method; add the destination computer to the WinRM TrustedHosts configuration setting or use HTTPS transport.
         Note that computers in the TrustedHosts list might not be authenticated.
        -For more information about WinRM configuration, run the following command: winrm help config. For more information, see the about_Remote_Troubleshooting Help topic.

    at System.Management.Automation.Runspaces.AsyncResult.EndInvoke()
    at System.Management.Automation.Runspaces.Internal.RunspacePoolInternal.EndOpen(IAsyncResult asyncResult)
    at System.Management.Automation.RemoteRunspace.Open()
    ...

Note: This has nothing to do with the credentials in WSManConnectionInfo - just the account settings in the service properties "Log On" tab.

I don't want to give the service admin privileges. Any ideas why the LocalSystem user fails to log in?

Additional info:

• The remote computer is not a member of a domain.
• I have tried to connect both by IP address and hostname (both are listed in the local computer's TrustedHosts).

EDIT: Even more info (summary of the comments):

• Local computer: Windows 7 Ultimate 64bit (virtual machine on a Windows 8 box).
• Remote computer: Windows Server 2008R2 Datacenter 64bit.
• The main reason we don't want to change service user accounts is that this is an update to an old service which is already deployed on many clients (customers).
• The service also accesses the Windows registry and the file system on the local computer, so setting the user account to something more restricted, like NetworkService, would just open a different can of worms.

A rather surprising solution to this one: The username in the PSCredential object (cred) needed to be prefixed with the domain-less remote computer's name, e.g. "MYREMOTESERVERNAME\remoteusername" and not just "remoteusername".

I have no idea why the prefix is needed only when connecting with the LocalSystem account though...