Query runs fast but occasionally never completes

I have messed things up at work (oh no!). Everything was running fine until about two days ago; queries executed instantly, and the database tended to sit around 20% load. Then I got told that some of our historical data in the database was entered incorrectly, and needed to be removed and re-entered from the following tables:

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)

My first attempt to delete the data simply took far too long – it's historical data so there are a few million rows. After that failed, I asked around and someone suggested disabling check constraints, deleting, and then re-enabling the constraints for those specific tables (which I will NEVER do again, terrible idea). The disable and delete ran fairly quickly, I had to leave the enable running all night but it did succeed.

From then on, the database has been at 100% CPU, and one of the queries occasionally never completes. It's the same query every time:

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

This query uses the index IX_TrackerId_DateRecorded_Processed, and usually takes no time at all to execute. Occasionally though, a query will just sit there executing until it times out (after 30 seconds).

So far, I have tried:

• Scaling the database up to 5 times the size (less timeouts, but still 100% CPU usage)
• Rebuilding the indexes, as they were fragmented to about 80% (no difference)
• Changing the query to isolation level READ UNCOMMITTED (no difference)

What could I possibly do to fix this?