Why is this key lookup required?
Have you updated statistics lately? Estimated Number Of Rows is 1 while Actual Number Of Rows is 10,259,536... Dated stats can lead to bad query plans (insufficient memory allocated for joins and sorts, bad join algorithm choices...).

When Auto Update Statistics is set to true on the database, SQL Server will automatically update statistics based on a percentage (around 20%) of changed rows in the statistic. This works well when tables are small but stats can get dated on bigger tables. A statistic in a table with 10000 records will automatically be updated when around 2000 of it's records get changed (and life is good). For a table with 10000000 records however, the auto update will still occur at 20% or 2000000 changed records (resulting in some very bad plans and long gaps between stat updates). 

With the release of SQL Server 2008 R2 SP1 (and all future versions) the threshold can be set to a dynamic value by using trace flag 2371. This addresses the big table problem. You can read more about it here: http://blogs.msdn.com/b/saponsqlserver/archive/2011/09/07/changes-to-automatic-update-statistics-in-sql-server-traceflag-2371.aspx