I guess NULLs are responsible for your problem. Try

...
	where callid not in(select phoneleadid
		from [67.xx.xxx.xxx].[server1].[dbo].[targettable]
                WHERE phoneleadid IS NOT NULL)

>The following query runs on the SQL server box that has 'sourcetable'. Its function is to add new records to 'targettable' on the remote linked server. It correctly adds rows when I have the column 'phoneleadid' as the primary key for 'targettable'. It runs, but does not add rows, if I change the primary key for 'targettable' and allow nulls in 'phoneleadid'. (There is no primary key on 'sourcetable'.)
>
>Any way to get this to run without having 'phoneleadid' be the primary key for 'targettable'? Would it be enough to disallow nulls in 'phoneleadid'?
>Thanks for any help.
>
>

>insert into [67.xx.xxx.xxx].[server1].[dbo].[targettable]
>	(phoneleadid,pnumber)
>	select callid,localuserid
>	from [sourcetable]
>	where callid not in(select phoneleadid
>		from [67.xx.xxx.xxx].[server1].[dbo].[targettable])
>