Poor Index Performance

Hey guys,

Having some trouble with indexes on sql server 2005. I'll explain it with a simplified example.
I have a customers table, and a sp to list customers :


create table Customers(
CusID int not null,
Name varchar(50) null,
Surname varchar(50) null,
CusNo int not null,
Deleted bit not null
)


create proc spCusLs (
@CusID int = null,
@Name varchar(50) = null,
@Surname varchar(50) = null,
@CusNo int = null
)
as

select
CusID,
Name,
Surname,
CusNo
from
Customers
where
Deleted = 0
and CusID <> 1000
and (@CusID is null or CusID = @CusID)
and (@CusNo is null or CusNo = @CusNo)
and (@Name is null or Name like @Name)
and (@Surname is null or Surname like @Surname)
order by
Name,
Surname


create nonclustered index ix_customers_name on customers ([name] asc)
with (sort_in_tempdb = off, drop_existing = off, ignore_dup_key = off, online = off) on primary

create nonclustered index ix_customers_surname on customers (surname asc)
with (sort_in_tempdb = off, drop_existing = off, ignore_dup_key = off, online = off) on primary

create nonclustered index ix_customers_cusno on customers (cusno asc)
with (sort_in_tempdb = off, drop_existing = off, ignore_dup_key = off, online = off) on primary



I've recently noticed that some tables, including 'Customers' don't have indexes except primary keys. And I have added indexes to "name", "surname" and "cusno" columns. This has dropped the number of IO reads. But the strange thing is; one time it works with name / surname searches like ('joh%' '%') but when CusNo is included, it does a full scan. And vice versa when the SP is recompiled using 'alter', works ok with CusNo, but not with name/surname. Recompile it, and it's reversed again. When run as a single query, the execution plan looks different.

What's happening? Perhaps something to do with statistics? This doesn't have a big payload on the server, but there are some other procs suffering from this on heavy queries, making server performance worse than before...