Index is seeked and scanned - is there a risk for seek to fail after modification? I have an index that has been seeked 230.000 times and scanned 130.000 times. 
In order to improve the queries that have scanned, because they use an additional column I guess, I would like to change the index and add the column that is  additionally used by the index-scanning query.

In the relevant index-scanning query both of the columns are used within a join operation as the joining columns.

Do I have to expect that the queries that so far seeked the index will afterwards fail to seek and scan the index instead? Should I instead add a seconde, new index?

CREATE TABLE [dbo].[ArtCatVRC](
[AVid] [uniqueidentifier] NOT NULL,
[ACatalID] [uniqueidentifier] NOT NULL,
[ACategID] [uniqueidentifier] NOT NULL, CONSTRAINT [PK_A] PRIMARY KEY NONCLUSTERED ([AVid] ASC, [ACatalID] ASC, [ACategID] ASC) WITH ... ON [PRIMARY] ) ON [PRIMARY]


Query (simplified):

Select V.Col1, V.Col2, C. ColN From ... AS C inner join ... AS V LEFT OUTER  JOIN dbo.ArtCatVRC AS R ON C.ID = R.ACategID AND R.ACatalID IN (V.X, V.Y, V.Z)


The used (scanned) index:

CREATE NONCLUSTERED INDEX [ACategId] ON [dbo].[ArtCatVRC] ( [ACategID] ASC )


After every execution of the above query, SYS.DM_DB_INDEX_USAGE_STATS increments SCANS +1 to this index.

The idea is to add the column R.ACatalID to the index, so that joining with both columns will change to seek the index.

Exec. Plan:

StmtText                                           
--------                                               
Stream Aggregate(GROUP BY:([cat].[ID])) 
|--Filter(WHERE:([DATABASE].[dbo].[ArtCatVRC].[AVid] as [R].[AVid] IS NULL))                                                                                                                                                                                                                                                                                         
           |--Merge Join(Right Outer Join, MANY-TO-MANY MERGE:([R].[ACategID])=([cat].[ID]), RESIDUAL:([DATABASE].[dbo].[T_ACateg].[ID] as [cat].[ID]=[DATABASE].[dbo].[ArtCatVRC].[ACategID] as [R].[ACategID] AND ([DATABASE].[dbo].[ArtCatVRC].[AVid] as [R].[AVid]=[DATABASE].[dbo].[T_ACatVM].[SS] as [viewMap].[SS] OR [DATABASE].[dbo].[ArtCatVRC].[AVid] as [R].[AVid]=[DATABASE].[dbo].[T_ACatVM].[SAVid] as [viewMap].[SAVid] OR [DATABASE].[dbo].[ArtCatVRC].[AVid] as [R].[AVid]=[DATABASE].[dbo].[T_ACatVM].[AVid] as [viewMap].[AVid]))) 
                |--Index Scan(OBJECT:([DATABASE].[dbo].[ArtCatVRC].[IX_ACategID_AVid] AS [R]), ORDERED FORWARD)                                                                                                                                                                         

                |--Sort(ORDER BY:([cat].[ID] ASC))                                                                                                                                                                                                                                                      
                     |--Nested Loops(Inner Join, OUTER REFERENCES:([viewMap].[ACatalID]))                                                                                                                                                                                                                  
                          |--Clustered Index Seek(OBJECT:([DATABASE].[dbo].[T_ACatVM].[IX_AVid] AS [viewMap]), SEEK:([viewMap].[AVid]={guid'00000000-0000-0000-0000-111122223333'}) ORDERED FORWARD)                                                                                                                                                                                                                                                         
                          |--Index Seek(OBJECT:([DATABASE].[dbo].[T_A_Categ].[IX_ACateg_ACatalID_Deleted_ID_DisOrd] AS [cat]), SEEK:([cat].[ACatalID]=[DATABASE].[dbo].[T_ACatVM].[ACatalID] as [viewMap].[ACatalID] AND [cat].[Deleted]=(0)) ORDERED FORWARD)
I would start by adding a clustered index to the table. Since the primary key is unique I would just update that from nonclustered to clustered. To do that you will have to drop and recreate the constraint so if you have foreign keys defined you will need to drop those constraints first then put them back once you have the primary key put back on.

A few references on clustered indexes

Clustered indexes vs heaps 

RID lookups

If all of your queries against the table include acatalid and acategid in the join or where clause then adding acatalid to the existing index may help.

However if the queries don't always include both columns in the where clause you may see a benefit in creating another index on acatalid. 

I say these changes may help as the statistics that SQL server has on the table could be generating an execution plan with the scan because it sees the cost of scanning through the table as less than doing a seek.