Generating the SQL query plan takes 5 minutes, the query itself runs in milliseconds. What's up?

You can try using a Plan Guide. Plan generation will still last some time, but should be significantly shorter.

Something will have caused the plan to require recompiling such as a statistics update or DDL change.The list if here: Execution Plan Caching and Reuse

The query in it's current form will always take 3-5 minutes to recompile: this can't be avoided.

Assuming you can't change it (PIVOT, use a trigger to maintain a "proper" table etc), then you can only control when the recompilation happens.

Remus' plan guide answer is one way. I'd also look at my statistic maintenance and ensure it's done overnight say, so it only happens once at start of day

Have you considered rewriting your 30-join SELECT to smth like this?

SELECT [key], NULL AS [a], NULL AS [b]  INTO #temp  FROM [pk-table]UPDATE t SET t.[a] = fk.[a], t.[b] = fk.[b]  FROM #temp t  INNER JOIN (    SELECT f.[key],      MAX(CASE WHEN f.[name] = 'a' THEN f.[value] ELSE NULL END) AS [a],      MAX(CASE WHEN f.[name] = 'b' THEN f.[value] ELSE NULL END) AS [b]    FROM [fk-table] f    GROUP BY f.[key]    ) fk ON (fk.[key] = t.[key]

Although it's maybe not an answer to your original question :)