Covering Index Changes Execution Plan but is not used

I have the following occasionally slow running query:

SELECT C.CustomerID  FROM dbo.Customers C WITH (NOLOCK) WHERE C.Forename = @Forename     AND C.Surname = @Surname OPTION (RECOMPILE) 

CustomerID is the Primary Key on the Customers table. The Customers table also has the following two non-clustered indexes:

CREATE NONCLUSTERED INDEX idx_Forename ON Customers (Forename ASC) CREATE NONCLUSTERED INDEX idx_Surname ON Customers (Surname ASC) 

When I run the query with both a surname and forename entered the query optimiser uses the index ‘idx_Surname’ as in the following execution plan:

Execution Plan without covering index

This query takes over two minutes to complete for this particular search and finds no results. For the values entered @Forename has no matches in the Customers table while @Surname matches 31,162 records. When I only search by the @surname the 31,162 records return in under a second with the following plan:

Execution Plan surname only search

In an attempt to optimise the query for searches containing both Forename and Surname I added the following covering index:

CREATE NONCLUSTERED INDEX idx_Surname_Covering ON dbo.Customers (Surname) INCLUDE (Forename) 

The query with both Forename and Surname then returns in less than one second. However, the covering index is not used in the actual execution plan:

Execution Plan with covering index

So,

  1. Is the covering index required or is there a better way to improve the performance and
  2. Why does the additional covering index cause the change of index in the actual execution plan from idx_Forename to idx_Surname?

p.s. the query above is an isolated example, when in use either surname or forename or both may be searched for and the Customers table also includes other searchable columns with their own indexes. This detail was not considered relevant to the question so I have not included it.