Finalmente, encontrei uma solução para esse problema. Configurei meu servidor como um web garden (aumento do número de processos de trabalho para 5) e o uso da CPU aumentou para 47%. Ainda não tenho certeza por que, mas meu palpite é que um grande número de solicitações ao banco de dados está preenchendo algum recurso que é limitado a um processo e aumentar o número de processos de trabalho pode resolver esse problema.
UPDATE
Eu encontrei a razão finalmente! Na configuração ServiceBehavior do meu serviço, tive InstanceContextMode.Single, enquanto o valor padrão de ConcurrencyMode também é Single. Eu mudei o último para múltiplos e está tudo bem agora.