unable to select certain records in TSQL without using a range, between, etc

Question

On a SQL Server 2008 R2 database I have a table with a single integer as a primary key. Sometimes when I perform a select on the primary key I get no results, but if I do a search for all records on the primary key between certain values I am able to retrieve the row. This only affects a few records (less than ten out of millions of rows). The vast majority of records can be selected with a simple "equals" statement.

Does anyone know what could be causing this or how to fix the problem? I suspect something may be wrong with the clustered index. If I use the hint "index(0)" then I can get the record without using a range.

Details:

Statement 1 produces no results:

select * from claim where claim_id = 12166769

Statement 2 produces one result for claim_id 12166769:

select * from claim where claim_id > 12166768 and claim_id < 12166770

Both statements use a Clustered Index Seek using PK_claim_claim_id.

Statement 3 produces one result for claim_id 12166769 using a hint:

select * from claim  with (index(0)) where claim_id = 12166769

The claim table has a column named "claim_id" defined as the primary key, integer, not null. It has a clustered index on the primary key named "PK_claim_claim_id".

I'm using SQL Sentry Plan Explorer to view the Plan Tree. Statement 1 has 1 Estimated Row and 0 Actual rows. Statement 2 has 7 Estimated rows and 1 Actual row.

Update Additionally we found that when we ran

select * from claim where claim_id > 12166774 and claim_id < 12166775

we came up five rows returned, 12166770 through 12166774. Running

select * from claim with (index(0))  where claim_id > 12166774 
and claim_id < 12166775

with the hint returned no records as expected.

6/22/2012 Update

I spoke too soon. We found this error in a different spot. I found that I hadn't actually scanned the entire database, only a portion of it.

select * from claim where claim_id in (8223749,8223752,8223753,8223754,8223755)

returns no rows, while

select * from claim with (index(0))
    where claim_id in (8223749,8223752,8223753,8223754,8223755)

returns rows. I ran

SELECT sys.fn_PhysLocFormatter(%%physloc%%),claim_id FROM claim with (index(0)) 
WHERE claim`_id in (8223749,8223752,8223753,8223754,8223755)

and received

(3:1394868:2)   8223749
(3:1394868:5)   8223752
(3:1394868:6)   8223753
(3:1394868:7)   8223754
(3:1394868:8)   8223755

Answer 1

Since my comment seemed to fix the problem I will go ahead and post as an answer.

DBCC CHECKTABLE ( table_name | view_name [ , { NOINDEX | index_id } |, { REPAIR_ALLOW_DATA_LOSS | REPAIR_FAST | REPAIR_REBUILD } ] )