SQL 7.0 - Query Not Using Index

I have a view (table_rol_contct) on a number of tables, one of which is a table of address data (table_address). This table has a unique, non-clustered index on Postcode, House Number and an Id column (idx_x_s_postcode). There is a clustered index on the Id column.

There are a number of queries which are run against this view, one of which selects addresses whose Postcode matches a full or partial Postcode entered through a Client Application.

This query :

Select distinct top 30
con.salutation+' '+con.first_name+' '+con.last_name as fullname,
con.title,
con.phone,
con.x_housename,
con.x_houseno,
con.x_housename+' '+con.x_houseno+' '+con.address+', '+con.address_2+' '+con.city as fulladdress,
from table_rol_contct con
where con.x_s_postcode like 'wf18%'
order by con.last_name asc, con.first_name asc

returns its results in under a second while this one:

Select distinct top 30
con.salutation+' '+con.first_name+' '+con.last_name as fullname,
con.title,
con.phone,
con.x_housename,
con.x_houseno,
con.x_housename+' '+con.x_houseno+' '+con.address+', '+con.address_2+' '+con.city as fulladdress,
from table_rol_contct con
where con.x_s_postcode like 'wf3%'
order by con.last_name asc, con.first_name asc

takes 38 seconds to returns its results.

The execution plans for these queries show that the slow query uses a Clustered Index Scan whereas the quick one uses an index seek on the ‘idx_x_s_postcode’ non-clustered index.

dbcc show_statistics (table_address, idx_x_s_postcode)

shows that this index has 300 steps with these representing the ones relevant to the above queries:

..., WF169AG, WF175NN, WF178BY, WF20HN, WF27ET, WF28TP, WF31PZ, WF34EF, WF42HL, ...

From this, you can see that ‘WF18%’ is wholly contained in a single step and the optimizer appears to happily perform an index seek, whereas ‘WF3%’ spans more than 1 so the optimizer seems to choose a clustered index scan.

Is there any way that I can force the use of the non-clustered index or, at least, make it more likely that the optimizer will use this index without coding an optimizer hint into the ‘Create View’ statement? The problem is that the view is used for other queries, all the queries run against it are generated from within a client application and the given search criteria could, for example, be ‘con.address’ rather than ‘con.x_s_postcode’.