Eu sei o que NewID() faz, só estou tentando entender como isso ajudaria na seleção aleatória. Será que (1) a instrução select irá selecionar TUDO da minha tabela, (2) para cada linha selecionada, adicionar um identificador único gerado por NewID(), (3) classificar as linhas por este identificador único e (4) selecionar as 100 primeiras da lista ordenada ?
Sim. isso está exatamente correto (exceto que não precisa necessariamente classificar todos as fileiras). Você pode verificar isso observando o plano de execução real.
SELECT TOP 100 *
FROM master..spt_values
ORDER BY NEWID()
O operador escalar de computação adiciona o
NEWID() coluna para cada linha (2506 na tabela na minha consulta de exemplo), as linhas na tabela são classificadas por esta coluna com as 100 principais selecionadas. Na verdade, o SQL Server não precisa classificar todo o conjunto das posições 100 para baixo, então ele usa um
TOP N operador de ordenação que tenta realizar toda a operação de ordenação na memória (para pequenos valores de N ) 
