Reducing Key Lookups

I am using SQL server, and I have been looking closely at the concept of key lookups, http://blog.sqlauthority.com/2009/10/07/sql-server-query-optimization-remove-bookmark-lookup-remove-rid-lookup-remove-key-lookup/ So if you have a key lookup you can create an index with the 'include' columns to cover the non index columns you have in the select statement. For instance, SELECT ID, FirstName FROM OneIndex WHERE City = 'Las Vegas' GO This index will include a key lookup, CREATE NONCLUSTERED INDEX [IX_OneIndex_City] ON [dbo].[OneIndex] ( [City] ASC ) ON [PRIMARY] GO But this one will remove the key lookup, CREATE NONCLUSTERED INDEX [IX_OneIndex_Include] ON [dbo].[OneIndex] ( City ) INCLUDE (FirstName,ID) ON [PRIMARY] GO I mean how much of an impact will this have on performance? The key lookup has an operator cost of 0.295969 (99%), but what does that really mean? How do you know that you need the second index there, and at what point does it become the case that you are trying to add too many indexes and it is not worth it? It seems to me that some queries can include index scans, key lookups, and still seem to perform very fast.