Q:

TSQL Iterate over table and perform sub query

Using a join with the openquery performs so badly in my case that iterating over a local table and performing a subquery sequentially is likely to be faster, however I don't know an appropriate way to do it. So far my attempt has been:
BEGIN
    CREATE TABLE #tmp
    (
        PayrollNo varchar(17)
    );
END 
GO

while(select InternalNo from [BUS].[dbo].[employees]) is not null
begin
    insert into #tmp select PayrollNo from openquery(CS, 'SELECT PD.PayrollNo FROM Payroll PD WHERE InternalNumber = ''' + InternalNo + '') OQ
end

So, iterating over a local table that holds employees I then select each payroll number based on each relating internal number.

A:

Are you sure that the JOIN is affecting performance so much?. Well, if you want to try iterating over the values of a table, then you can use a cursor:
DECLARE @InternalNo INT -- Use the correct data type
DECLARE @Query VARCHAR(MAX);

DECLARE CC CURSOR FOR
SELECT InternalNo 
FROM [BUS].[dbo].[employees]

OPEN CC
FETCH NEXT FROM CC INTO @InternalNo
WHILE @@FETCH_STATUS = 0
BEGIN
    SET @Query = '  SELECT PayrollNo
                    FROM OPENQUERY( CS, 
                                    ''SELECT PD.PayrollNo 
                                      FROM Payroll PD 
                                      WHERE InternalNumber = ' + CAST(@InternalNo AS VARCHAR(10)) + ''') OQ'

    INSERT INTO #tmp
    EXEC(@Query)

    FETCH NEXT FROM CC INTO @InternalNo
END
CLOSE CC
DEALLOCATE CC

You can test both options and choose which one is better.

