SQL Linked Server returns error "no login-mapping exists" when non-admin account is used

UPDATE: See @Anton's and @Wouter's answer for alternative solution.

According to this blog, I have to specify User ID in the provider string if non-sysadmin accounts are used. Here is an example.

EXEC master.dbo.sp_addlinkedserver 
    @server = N'MyLinkServerName',
    @provider = N'SQLNCLI',
    @srvproduct = 'SQLNCLI',
    @provstr = N'SERVER=MyServerName\MyInstanceName;User ID=myUser'

This exactly matches what I have encountered and it solves my problem.

As alternative solution you can use the parameter @datasrc instead of @provstr. @dataSrc works without setting the User ID

Sample:

EXEC master.dbo.sp_addlinkedserver @server = N'LinkServerName', @provider=N'SQLNCLI',@srvproduct = 'MS SQL Server', @datasrc=N'serverName\InstanceName' 
EXEC master.dbo.sp_addlinkedsrvlogin @rmtsrvname = N'LinkServerName', @locallogin = NULL , @useself = N'False', @rmtuser = N'myUser', @rmtpassword = N'*****'

I've added a comment here, too, but it's not visible (don't know why).

After playing around with this, i found that you can avoid having to use the User ID property altogether, by using @datasrc instead of @provstr. This is very poorly documented, but the example below works for me:

EXEC master.dbo.sp_addlinkedserver
    @server = 'SOME_NAME',
    @srvproduct='', -- needs to be explicitly empty, default is NULL and is not allowed
    @datasrc='some_server.com\SOME_INSTANCE',
    @provider='SQLNCLI';

-- Set up the Linked server to pass along login credentials
EXEC master.dbo.sp_addlinkedsrvlogin
    @rmtsrvname='SOME_NAME',
    @useself='true', -- Optional. This is the default
    @locallogin=NULL; -- Optional. This is the default

Using this method you can reuse the same Linked server for all of your users. The currently accepted answer has the huge drawback that you need to set up a separate linked server for each user.