Seek and you shall Scan... on partitioned tables
The basic issue is that the Index Seek is not followed by a Top operator. This is an optimization that is usually introduced when the seek returns rows in the correct order for a MIN\MAX aggregate.

This optimization exploits the fact that the min/max row is the first one in ascending or descending order. It may also be that the optimizer cannot apply this optimization to partitioned tables; I forget.

Anyway, the point is that without this transformation, the execution plan ends up processing every row that qualifies S.UpdatedID &lt;= @IDColumnThresholdValue per partition, rather than the desired one row per partition.

You have not provided table, index, or partitioning definitions in the question so I can't be much more specific. You should check that your index would support such a transformation. More or less equivalently, you could also express the MAX as a TOP (1) ... ORDER BY UpdatedID DESC.

If this results in a Sort (including a TopN Sort), you know your index is not helpful. For example:

SELECT
    @MaxIDPartitionTable = ISNULL(MAX(T2.IDPartitionedTable), 0)
FROM    
( 
    SELECT
        O.IDPartitionedTable
    FROM      
    ( 
        SELECT
            P.partition_number AS PartitionNumber
        FROM sys.partitions AS P
        WHERE 
            P.[object_id] = OBJECT_ID(N'fct.MyTable', N'U')
            AND P.index_id = 1
    ) AS T1
    CROSS APPLY 
    (    
        SELECT TOP (1) 
            S.UpdatedID AS IDPartitionedTable
        FROM fct.MyTable AS S
        WHERE
            $PARTITION.PF_MyTable(S.PCTimeStamp) = T1.PartitionNumber
            AND S.UpdatedID &lt;= @IDColumnThresholdValue
        ORDER BY
            S.UpdatedID DESC
    ) AS O
) AS T2;


The plan shape this should produce is:



Notice the Top below the Index Seek. This limits the processing to one row per partition.

Or, using a temporary table to hold partition numbers:

CREATE TABLE #Partitions
(
    partition_number integer PRIMARY KEY CLUSTERED
);

INSERT #Partitions
    (partition_number)
SELECT
    P.partition_number AS PartitionNumber
FROM sys.partitions AS P
WHERE 
    P.[object_id] = OBJECT_ID(N'fct.MyTable', N'U')
    AND P.index_id = 1;

SELECT
    @MaxIDPartitionTable = ISNULL(MAX(T2.UpdatedID), 0)
FROM #Partitions AS P
CROSS APPLY 
(
    SELECT TOP (1) 
        S.UpdatedID
    FROM fct.MyTable AS S
    WHERE
        $PARTITION.PF_MyTable(S.PCTimeStamp) = P.partition_number
        AND S.UpdatedID &lt;= @IDColumnThresholdValue
    ORDER BY
        S.UpdatedID DESC
) AS T2;

DROP TABLE #Partitions;


Side note: accessing a system table in your query prevents parallelism. If this is important, consider materializing the partition numbers in a temporary table, then APPLY from that. Parallelism is not normally helpful in this pattern (with correct indexing) but it would be remiss of me not to mention it.

Side note 2: There is an active Connect item requesting built-in support for MIN\MAX aggregates and Top on partitioned objects.