A consulta é executada rapidamente, mas ocasionalmente nunca é concluída

Eu estraguei as coisas no trabalho (oh não!). Tudo estava indo bem até cerca de dois dias atrás; consultas executadas instantaneamente, e o banco de dados tendia a ficar em torno de 20% da carga. Então me disseram que alguns de nossos dados históricos no banco de dados foram inseridos incorretamente e precisavam ser removidos e reinseridos nas seguintes tabelas:

CREATE TABLE TrackerStates(
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [TrackerId] [int] NOT NULL,
    [DateRecorded] [datetime] NOT NULL,
    [Latitude] [float] NOT NULL,
    [Longitude] [float] NOT NULL,
    [Altitude] [float] NOT NULL,
    -- Some other fields
    CONSTRAINT [PK_dbo.TrackerStates] PRIMARY KEY NONCLUSTERED  (Id)
)

CREATE CLUSTERED INDEX IX_TrackerId_DateRecorded_Processed ON TrackerStates (TrackerId, DateRecorded, Processed)
CREATE NONCLUSTERED INDEX IX_TrackerId_Processed ON TrackerStates (TrackerId) WHERE (Processed = 0)

CREATE TABLE TrackingPoints(
    [DatabaseId] [int] NOT NULL,
    [TrackerStateId] [int] NOT NULL,
    [RoadId] [int] NOT NULL,
    [Distance] [float] NOT NULL,
    PRIMARY KEY CLUSTERED (DatabaseId, TrackerStateId),
    FOREIGN KEY (DatabaseId) REFERENCES RammDatabases (Id),
    FOREIGN KEY (TrackerStateId) REFERENCES TrackerStates (Id)
)
CREATE NONCLUSTERED INDEX IX_DatabaseId ON TrackingPoints (DatabaseId)
CREATE NONCLUSTERED INDEX IX_TrackerStateId ON TrackingPoints (TrackerStateId)

CREATE TABLE TrackingSegments(
    [DatabaseId] [int] NOT NULL,
    [StartingStateId] [int] NOT NULL,
    [EndingStateId] [int] NOT NULL,
    [EntityId] [nvarchar](max) NULL,
    PRIMARY KEY CLUSTERED (DatabaseId, StartingStateId, EndingStateId),
    FOREIGN KEY (DatabaseId) REFERENCES RammDatabases (Id),
    FOREIGN KEY (StartingStateId) REFERENCES TrackerStates (Id),
    FOREIGN KEY (EndingStateId) REFERENCES TrackerStates (Id),
    FOREIGN KEY (DatabaseId, StartingStateId) REFERENCES TrackingPoints (DatabaseId, TrackerStateId),
    FOREIGN KEY (DatabaseId, EndingStateId) REFERENCES TrackingPoints (DatabaseId, TrackerStateId)
)
CREATE NONCLUSTERED INDEX IX_DatabaseId ON TrackingSegments (DatabaseId)
CREATE NONCLUSTERED INDEX IX_DatabaseId_StartingStateId ON TrackingSegments (DatabaseId, StartingStateId)
CREATE NONCLUSTERED INDEX IX_DatabaseId_EndingStateId ON TrackingSegments (DatabaseId, EndingStateId)

Minha primeira tentativa de excluir os dados simplesmente demorou muito - são dados históricos, então há alguns milhões de linhas. Depois que isso falhou, perguntei por aí e alguém sugeriu desabilitar restrições de verificação, excluir e reativar as restrições para essas tabelas específicas (o que NUNCA farei novamente, péssima ideia). A desativação e a exclusão foram executadas rapidamente, tive que deixar a ativação em execução a noite toda, mas foi bem-sucedida.

A partir de então, o banco de dados está com 100% de CPU e uma das consultas ocasionalmente nunca é concluída. É a mesma consulta todas as vezes:

SELECT TOP 500 * FROM TrackerStates WHERE TrackerId = @TrackerId AND Processed = 0 ORDER BY DateRecorded

Essa consulta usa o índice IX_TrackerId_DateRecorded_Processede geralmente não leva tempo para ser executada. Ocasionalmente, porém, uma consulta ficará lá executando até atingir o tempo limite (após 30 segundos).

Até agora, tentei:

• Escalar o banco de dados em até 5 vezes o tamanho (menos tempos limite, mas ainda com 100% de uso da CPU)
• Reconstruindo os índices, pois estavam fragmentados para cerca de 80% (sem diferença)
• Alterando a consulta para o nível de isolamento READ UNCOMMITTED(sem diferença)

O que eu poderia fazer para consertar isso?