Sql-server – Why does this CTE return the bulk of its results immediately, but then take several minutes to finish

I've got a schema roughly like this (this is a simplification of my actual schema):

CREATE TABLE foo (
    key1 NUMERIC(6) NOT NULL,
    key2 VARCHAR(32) NOT NULL,
    val VARCHAR(255) NULL,
    CONSTRAINT foo_pk PRIMARY KEY (key1, key2) --PK on key1, key2
    )
GO
CREATE TABLE bar (
    key1 NUMERIC(6) NOT NULL,
    key2 VARCHAR(32) NOT NULL,
    val VARCHAR(255) NULL,
    CONSTRAINT bar_pk PRIMARY KEY (key1, key2) --PK on key1, key2
    )
GO
CREATE TABLE aliases (
    id VARCHAR(32) NOT NULL PRIMARY KEY,
    text VARCHAR(255) NOT NULL,
    CONSTRAINT aliases_uk UNIQUE (text) --PK on id, unique constraint on text
    )
GO

INSERT INTO aliases (id, text)
SELECT REPLACE(NEWID(), '-', ''), 'Text1' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text2' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text3' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text4' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text5' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text6' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text7' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text8' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text9' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text10' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text11' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text12' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text13' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text14' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text15' UNION ALL
SELECT REPLACE(NEWID(), '-', ''), 'Text16';
GO

BEGIN
    DECLARE @i INT = 1;
    WHILE (@i <= 234)
    BEGIN
        INSERT INTO foo (key1, key2, val) SELECT @i, id, id FROM aliases;
        SET @i = @i + 1;
    END;
    INSERT INTO bar (key1, key2, val) SELECT key1 + 234, key2, val FROM foo;
END;
GO

I want to get a list of all key1 and key2 pairs (using the user-friendly names for key2, with the user-friendly aliases for the vals concatenated. My initial attempt looks like this:

WITH
foos_and_bars (key1, key2, val) AS (
    SELECT key1, key2, val FROM foo UNION ALL
    SELECT key1, key2, val FROM bar),
texts (key1, key2_name, val_text, rnum) AS (
    SELECT key1, a1.text, a2.text, ROW_NUMBER() OVER (PARTITION BY key1, key2 ORDER BY val)
    FROM foos_and_bars
    JOIN aliases a1 ON a1.id = foos_and_bars.key2
    LEFT JOIN aliases a2 ON a2.id = foos_and_bars.val),
partitioned (key1, key2_name, val_text, rnum, maxnum) AS (
    SELECT key1, key2_name, val_text, rnum, MAX(rnum) OVER (PARTITION BY key1, key2_name)
    FROM texts),
recurse (key1, key2_name, val_texts, rnum, maxnum) AS (
    SELECT key1, key2_name, val_text, rnum, maxnum
    FROM partitioned
    WHERE rnum = 1
    UNION ALL
    SELECT r.key1,
        r.key2_name, 
        CAST(r.val_texts + CHAR(13) + CHAR(10) + p.val_text AS VARCHAR(255)),
        p.rnum,
        r.maxnum
    FROM recurse r
    JOIN partitioned p
    ON p.key1 = r.key1
    AND p.key2_name = r.key2_name
    AND p.rnum = r.rnum + 1)
SELECT * FROM recurse WHERE rnum = maxnum;

It works, and I get 7480 rows in less than a second, but then SSMS runs for no less than 2 minutes and 40 seconds puzzling out the last 8 rows. These last rows are no more complex than the first (in fact, with the data currently in the system, rnum and maxnum are never greater than 1), and as these tables were created exclusively for mocking on this SE question, there should be no locks.

The issue seems to be limited to the recursive CTE, as selecting from the top down to partitioned yields 7488 rows in less than a second. What could the CTE be getting stuck on?

Execution plans (using a setup that matches the simplified schema):

• Plan for all records
• Records for only one key1

The output is going into a view that is going to back a Sybase window, which will be used for searching records. As such, it needs to be capable of retrieving all the rows, though the program pulls 1000 rows at a time by default.