Debe obligar al motor de la base de datos a evaluar un nuevo valor para cada fila. Puede hacer esto agregando una cláusula ficticia where en la tabla externa como:
DECLARE @city TABLE(ID INT IDENTITY(1, 1), City VARCHAR(100))
INSERT INTO @city VALUES
('Dallas'),
('New York'),
('Washington'),
('Las Vegas')
DECLARE @random TABLE(ID INT IDENTITY(1, 1), City VARCHAR(100))
INSERT INTO @random VALUES
('Manchester'),
('London'),
('Oxford'),
('Liverpool')
SELECT * FROM @city c
CROSS APPLY(SELECT TOP 1 * FROM @random r WHERE c.ID = c.ID ORDER BY NEWID()) ca
si elimina WHERE c.ID = c.ID
obtendrá el mismo valor para todas las filas.