sibvic

Похоже опять сработала методология Rubber Duck Programming. В моем случае помог фильтр на индекс
Индекс

CREATE NONCLUSTERED INDEX [IX_...]
    ON [dbo].[Table]([Processed] ASC, [RecordType] ASC);

изменил на

CREATE NONCLUSTERED INDEX [IX_...]
    ON [dbo].[Table]([Processed] ASC, [RecordType] ASC) WHERE ([Processed]=(0));

Ну либо в EF:

protected override void OnModelCreating(ModelBuilder builder)
        {
            base.OnModelCreating(builder);
            builder.Entity<Table>()
                .HasIndex(x => new { x.Processed, x.RecordType})
                .HasFilter("Processed= 0")//NEW!!!
                .IsUnique(false);
        }

Теперь оба запроса выролняются одинаково быстро