Creating Indexes On Large Table To Increase Performance

Dear all,
I'm using SQL Server 2005 Standard Edetion.
I have the following stored procedure that is executed against two tables (RecrodedCalls) and (RecordedCallsTags)
The table RecordedCalls has more than 10000000 Records and RecordedCallsTags is about 7500000 Records
Now the lines marked in baby blue are dynamic (Dynamic where statement) that varies every time this stored procedure is executed, may it contains 7 columns in condetion statement or may it contains 10 columns, or 2 coulmns.....etc
Now I want to create non-clustered indexes on the columns used in the where statement, THE DTA suggests different indexing whenever the where statement changes.
So what is the right way to created indexes, to create one index on all the columns once, or to create separate indexes on each columns, sometimes the DTA suggests 5 columns together at one if I€™m using 5 conditions, I can€™t accumulate all the possible indexes hence the where statement always vary from situation to situation, below the SP:


CREATE TABLE #tempLookups (ID int identity(0,1),Code NVARCHAR(100),NameE NVARCHAR(500),NameA NVARCHAR(500))

CREATE TABLE #tempTable (ID int identity(0,1),TypesCount INT,CallsType NVARCHAR(50))



INSERT INTO #tempLookups SELECT Code, NameE, NameA FROM lookups WHERE [Type] = 'CALLTYPES' ORDER BY Ordering ASC

INSERT INTO #tempTable SELECT COUNT(DISTINCT(RecordedCalls.ID)) As TypesCount,RecordedCalls.CallType as CallsType

FROM RecordedCalls LEFT OUTER JOIN RecordedCallsTags ON RecordedCalls.ID = RecordedCallsTags.CallID

WHERE RecordedCalls.ID <= '9369907'

AND (RecordedCalls.CallDate BETWEEN cast ('01 Jan 1910 00:00:00:000' as datetime ) AND cast ( '01 Jan 2210 00:00:00:000' as datetime ))

AND (RecordedCalls.Duration BETWEEN 0 AND 1000000)

AND RecordedCalls.ChannelID NOT IN('62061','62062','62063','62064','64110','64111','64112','64113','64114','69860','69861','69862','69863','69866','69867','69868')

AND RecordedCalls.ServerID NOT IN('2')

AND RecordedCalls.AgentID NOT IN('1000010000')

AND (RecordedCallsTags.TagID is null OR RecordedCallsTags.TagID NOT IN('100','200'))

AND RecordedCalls.IsDeleted='false'

GROUP BY RecordedCalls.CallType

SELECT IsNull(#tempTable.TypesCount, 0) AS TypesCount, CASE('English')

WHEN 'Arabic' THEN #tempLookups.NameA

ELSE #tempLookups.NameE

END AS CallsType FROM

#tempTable RIGHT OUTER JOIN #tempLookups ON #tempTable.CallsType = #tempLookups.Code

DROP TABLE #tempLookups

DROP TABLE #tempTable


Thanks all,
Tayseer

Any suggestions how to create efficient indexes??!!