with clause execution order

In a simplified scenario I have table T that looks somthing like:

Key  Value
1    NULL
1    NULL
1    NULL
2    NULL
2    NULL
3    NULL
3    NULL

I also have a very time-consuming function Foo(Key) which must be considered as a black box (I must use it, I can't change it).

I want to update table T but in a more efficient way than

UPDATE T SET Value = dbo.Foo(Key)

Basically I would execute Foo only one time for each Key.

I tried something like

WITH Tmp1 AS
(
   SELECT DISTINCT Key FROM T
)
, Tmp2 AS
(
   SELECT Key, Foo(Key) Value FROM Tmp1
)
UPDATE T
SET T.Value = Tmp2.Value
FROM T JOIN Tmp2 ON T.Key = Tmp2.Key

but unexpectedly computing time doesn't change at all, because Sql Server seems to run Foo again on every row.

Any idea to solve this without other temporary tables?