Sql-server – Clustered Index Scan when using greater than in WHERE clause

I have the following table

create table t1(
col1 varchar(255) NOT NULL,
col2 varchar(255) NULL,
col3 bigint NULL,
CONSTRAINT PK_t1 PRIMARY KEY CLUSTERED
 (
   col1 asc
 )
)

CREATE NONCLUSTERED INDEX I_col3 ON t1(col3 desc)

This table has ~10000 rows with col2 always being populated and col3 has varying percentages of rows that are NOT NULL.

I am running the following query

DECLARE @number bigint
SET @number = 123456
SELECT col1, col2 FROM t1
WHERE col3 > @number

SQL is always generating a execution plan with a clustered index scan.

Now if I run the query as an adhoc query SQl does an index seek on I_col3 with a key lookup

SELECT col1, col2 FROM t1
WHERE col3 > 123456

The value being passed in the WHERE clause results in a small number of rows being returned (e.g. 3)

When running the ad-hoc query the execution plan shows the Estimated Number of Rows as 3.32. However, when I run the parameterized query it shows 2796 estimated rows.

If I add an index hint to the ad-hoc query it still shows 2796 estimated rows (not that I expect this to change) but it does do an index seek. When comparing the number of logical reads between the ad-hoc and parameterized query the
Parameterized Query:
Scan count 1, logical reads 89, physical reads 1, read-ahead reads 64, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Ad-Hoc Query
Scan count 1, logical reads 8, physical reads 1, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

And when forcing the index using the index hint
Scan count 1, logical reads 12, physical reads 1, read-ahead reads 18, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

I'm currently running SQl 2014 CP1-CU5. I've tried using trace flag 9184 to force SQL to use the old cardinality estimator which reduces the estimated rows to 1627 but still does a clustered index scan. I've also tried on SQL 2008 R2 and it has the same behavior as SQL 2014 with trace flag 9184.

In between each iteration of the query I am clearing the procedure cache and buffer pool.

I should also noted that I have also tried the following

1. Filtered INDEX on col3 WHERE NOT NULL
2. Filtered STATS on col3 WHERE NOT NULL

I've also done a full rebuild on the both the clustered and non clustered indexes and verified that stats are up to date.

Any suggestions or ideas?

Thanks again

UPDATE:
From reading through some links from Martin's answer I found the following blog post:

http://www.sqlskills.com/blogs/kimberly/exec-and-sp_executesql-how-are-they-different/

I confirmed that using sp_executesql or exec(@sql) does result in an index seek execution plan being generated and reused regardless of what the parameter value(s) are.

DECLARE @sql nvarchar(max)
SELECT @sql = 'SELECT col1, col2, FROM t1 WHERE col3 > @number'
EXEC sp_executesql @sql, N'@number bigint', @number = 123456789