Query performance and join hints, plan cost, and duration

Question

Having some trouble identifying why a query's duration would decrease when using OPTION (HASH JOIN) or OPTION (MERGE JOIN), although plan cost increases.

Background

I have a reporting database using traditional star schema (dimension/fact tables). SQL is generated by ORM in the BI tool. I have some flexibility with the generated SQL in terms of adding optimizer hints, but that's it (no query refactoring, etc.).

Problem

When the below query is executed with no optimizer hints, average duration is around 90 seconds and estimated subtree cost is around 2.9. When executed with the OPTION (MERGE JOIN) or OPTION (HASH JOIN) hints, average duration is around 3 seconds, but estimated subtree cost is around 4.9.

I have verified that statistics on affected tables are up to date using UPDATE STATISTICS <schema>.<table> WITH FULLSCAN;. Indexes have also been added based on optimizer recommendations.

Here's the query (yes, it's ugly, see ORM comment above):

SELECT  a11.trans_00_key  TRANS_00_KEY,
    a11.region_id  REGION_ID,
    Max(a15.region_cd)  REGION_CD,
    a11.state_id  STATE_ID,
    Max(a13.district_cd)  DISTRICT_CD,
    a12.cntrct_nbr  CNTRCT_NBR,
    a11.proj_nbr  PROJ_NBR,
    Max(a11.proj_nbr)  PROJ_NBR0,
    CONVERT(DATETIME, CONVERT(VARCHAR(10), (a12.sys_date_yr + '-' + a12.sys_date_mon + '-01'), 101))  CustCol_5,
    a12.proj_ctgry_nbr  PROJ_CTGRY_NBR,
    a11.type_of_work  TYPE_OF_WORK,
    a11.funct_rng  FUNCT_RNG,
    Isnull(a11.fis_id, -1)  FIS_ID,
    Max(Isnull(a14.fis_dscr, 'Blank'))  FIS_DSCR,
    CASE WHEN a12.bid_amount > 1 THEN a12.bid_amount ELSE a12.eng_est_amt END  CustCol_7,
    Sum(a11.est_amt)  WJXBFS1,
    (Sum(a11.ltd_amt) - (Sum(a11.ltd_ind_bill_cst) + Sum(a11.ltd_ind_non_bill_cst)))  WJXBFS2,
    Sum(a11.ltd_cost_cntrct)  WJXBFS3,
    ((Sum(a11.ltd_amt) - (Sum(a11.ltd_ind_bill_cst) + Sum(a11.ltd_ind_non_bill_cst))) - Sum(a11.ltd_cost_cntrct))  WJXBFS4,
    (Sum(a11.est_amt) - (Sum(a11.ltd_amt) - (Sum(a11.ltd_ind_bill_cst) + Sum(a11.ltd_ind_non_bill_cst))))  WJXBFS5
FROM    sys_trans_detail_fact   a11
    JOIN    sys_trans_hdr_fact  a12
      ON    (a11.proj_nbr = a12.proj_nbr AND
    a11.trans_00_key = a12.trans_00_key AND
    a11.state_id = a12.state_id)
    JOIN    district_lkp    a13
      ON    (a11.state_id = a13.state_id)
    JOIN    fis_lkp a14
      ON    (Isnull(a11.fis_id, -1) = Isnull(a14.fis_id, -1))
    JOIN    region_lkp  a15
      ON    (a11.region_id = a15.region_id)
WHERE   (((a11.trans_00_key)
 IN (SELECT r12.trans_00_key
    FROM    sys_trans_detail_fact   r12
    WHERE   r12.fund_src_name_id IN (3, 7, 5)))
 AND a11.fund_src_name_id IN (6, 8, 2, 3, 7, 5, 4)
 AND a11.state_id IN (8, 4, 19, 14, 20, 23, 17, 25, 16, 18, 24, 2, 12, 22, 5, 11, 6, 1, 21, 7, 15, 10, 9, 3, 13, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
 AND a11.status_id = 1
 AND a11.extract_dttm IN (CONVERT(DATETIME, '2012-09-01 00:00:00', 120))
 AND a11.cost_cat_id IN (10, 4))
GROUP BY    a11.trans_00_key,
    a11.region_id,
    a11.state_id,
    a12.cntrct_nbr,
    a11.proj_nbr,
    CONVERT(DATETIME, CONVERT(VARCHAR(10), (a12.sys_date_yr + '-' + a12.sys_date_mon + '-01'), 101)),
    a12.proj_ctgry_nbr,
    a11.type_of_work,
    a11.funct_rng,
    Isnull(a11.fis_id, -1),
    CASE WHEN a12.bid_amount > 1 THEN a12.bid_amount ELSE a12.eng_est_amt END

Actual execution plan with no hints

I'm confused as to why the plan shows 572 million actual rows for the index seek outlined in red.

Actual execution plan using OPTION (HASH JOIN) hint

I've read that optimizer hints are a last resort after verifying appropriate indexes have been applied and statistics are verified up-to-date. In this case, SQL Server seems to be picking the best plan based on cost, but there is a significant (about 87 second) penalty in terms of query duration. Does this sound like a case where the optimizer hint should be used? If not, what other items should I check to ensure the optimizer picks the best plan for cost and duration?