How to avoid cluster index scan?

Question

I've a table with a few millions of records. Here's the table structure:

Column_name	Type	Computed	Length	Prec	Scale	Nullable	TrimTrailingBlanks	FixedLenNullInSource	Collation
Id	int	no	4	10	0	no	(n/a)	(n/a)	NULL
A	nvarchar	no	510			yes	(n/a)	(n/a)	French_CI_AS
B	nvarchar	no	128			yes	(n/a)	(n/a)	French_CI_AS
C	datetime2	no	8	27	7	yes	(n/a)	(n/a)	NULL
D	nvarchar	no	510			yes	(n/a)	(n/a)	French_CI_AS
E	datetime2	no	8	27	7	no	(n/a)	(n/a)	NULL
F	nvarchar	no	1024			yes	(n/a)	(n/a)	French_CI_AS
G	nvarchar	no	510			yes	(n/a)	(n/a)	French_CI_AS
H	nvarchar	no	510			yes	(n/a)	(n/a)	French_CI_AS
I	nvarchar	no	32			yes	(n/a)	(n/a)	French_CI_AS
J	nvarchar	no	-1			no	(n/a)	(n/a)	French_CI_AS
K	int	no	4	10	0	yes	(n/a)	(n/a)	NULL
L	nvarchar	no	510			yes	(n/a)	(n/a)	French_CI_AS
M	nvarchar	no	-1			yes	(n/a)	(n/a)	French_CI_AS
N	int	no	4	10	0	yes	(n/a)	(n/a)	NULL
O	varchar	no	250			yes	no	yes	French_CI_AS
P	varchar	no	250			yes	no	yes	French_CI_AS
Q	varchar	no	250			yes	no	yes	French_CI_AS

Here's the query generated by EF :

(@p__linq__0 nvarchar(4000),@p__linq__1 nvarchar(4000))SELECT TOP (1) 
    [Project1].[Id] AS [Id], 
    [Project1].[A] AS [A], [Project1].[B] AS [B], [Project1].[C] AS [C], [Project1].[D] AS [D], 
    [Project1].[E] AS [E], [Project1].[F] AS [F], [Project1].[G] AS [G], [Project1].[H] AS [H], 
    [Project1].[I] AS [I], [Project1].[J] AS [J], [Project1].[K] AS [K], [Project1].[L] AS [L], 
    [Project1].[M] AS [M], [Project1].[N] AS [N], [Project1].[O] AS [O], [Project1].[P] AS [P], 
    [Project1].[S] AS [S]
    FROM ( SELECT 
        [Extent1].[Id] AS [Id], 
        [Extent1].[A] AS [A], [Extent1].[B] AS [B], [Extent1].[C] AS [C], [Extent1].[D] AS [D], 
        [Extent1].[E] AS [E], [Extent1].[F] AS [F], [Extent1].[G] AS [G], [Extent1].[H] AS [H], 
        [Extent1].[I] AS [I], [Extent1].[J] AS [J], [Extent1].[K] AS [K], [Extent1].[L] AS [L], 
        [Extent1].[M] AS [M], [Extent1].[N] AS [N], [Extent1].[O] AS [O], [Extent1].[P] AS [P], 
        [Extent1].[S] AS [S]
        FROM [dbo].[MyTable] AS [Extent1]
        WHERE (@p__linq__0 = [Extent1].[L]) OR ((@p__linq__0 IS NULL) AND ([Extent1].[L] IS NULL)) OR (@p__linq__1 = [Extent1].[L]) OR ((@p__linq__1 IS NULL) AND ([Extent1].[L] IS NULL))
    )  AS [Project1]
    ORDER BY [Project1].[Id] ASC

Of course, I've an index on the column L.

Almost every query execution is fine, but, sometimes, for a reason I can't explain, it uses the following plan (a Clustered Index Scan on the PK) and ends in a timeout:

Is there anything I can do to avoid this terrible choice? Am I in the obligation to create a plan guide?

Here's the problematic plan, and here's the working one;

Here's the C# code:

string a = "SomeValue";
string b = "SomeOtherValue"
var entity = service.GetAll()
    .Where(x => a == x.L || b == x.L)
    .OrderBy(x => x.Id)
    .FirstOrDefault();