Please post the following:

DDL for the two tables, including the indexes (leave off extended properties if you have those)

Actual execution plans for the good and bad query executions. Save the plans as .SQLPLAN files and attach them to a post on this thread.