CTE query that fails to find ancestors

I believe you made a mistake in your join predicate. Try:

WITH chainIDsUpwards AS
    (
        SELECT id, parent_id FROM foo WHERE id = @starting_id

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsUpwards p ON p.parent_id = foo.id
    )

    SELECT id FROM chainIDsUpwards

It is a common mistake, and I often do it myself. I find it easiest to get it right if I start with the CTE:

    SELECT foo.id, foo.parent_id 
    FROM chainIDsUpwards p
    JOIN foo p 

and then think of the CTE as a linked list where I need to find the next element:

        ON p.parent_id = foo.id