SQL Server Fulltext search against big amount of search terms over some period of time
Execution plan XML would be useful here but as a shot in the dark:


Daft as it may sound, try pushing either the [id] or date predicate into the CONTAINSTABLE query. See SQL Server 2005 Full-Text Queries on Large Catalogs: Lessons Learned - Consider embedding filter conditions as keywords in the indexed text.
I don't remember where but I recall reading an article or blog post some time ago that flagged big OR full-text queries as problematic. IIRC the suggested hack/workaround was to issue a UNION query instead.


For your example, the UNION for 2) would be along the lines of:

INSERT
    @processed_rules
    (
    rule_id
    , story_id
    )
SELECT
    @rule_id
  , s.[key]
FROM
   CONTAINSTABLE(Stories, (header, body), '"term one"')

UNION

SELECT
    @rule_id
  , s.[key]
FROM
   CONTAINSTABLE(Stories, (header, body), '"term two"')

UNION

  SELECT
    @rule_id
  , s.[key]
FROM
   CONTAINSTABLE(Stories, (header, body), '"term three"')