Você tem um plano de manutenção automatizado para atualizar estatísticas, reconstruir índices, etc.? Caso contrário, o SQL Server ainda pode estar construindo seus planos de consulta em suas estatísticas mais antigas de tabelas menores.

O SQL Server gera planos de consulta paralela automaticamente, se determinadas condições forem atendidas. De um artigo no MSDN :

Outros fatores:

O SQL Server está configurado para ter afinidade com um único processador?

A opção de grau máximo de paralelismo está definida como 1?

-- EDITAR --

Você já tentou perfilar esse processo? Seria interessante ver o plano de consulta que o SQL Server gera.

Você tem um código de exemplo para postar?

Se você tiver um trabalho de backup noturno automatizado, pode simplesmente restaurar o backup para o arquivo morto?