I was going to look into a 'Plan Guide' to see if I could force the replication stored procedure to use the same clustered index seek that the query uses when I manually execute it, but I think I found another solution.

I created a second nonclustered index on the primary key column for the table article. Normally I think this would be redundant and a little silly, but now the call to sp_MSenumchanges_belongtopartition returns a batch of 100 rows in a few ms instead of 10 minutes. No idea why this fixed it, but it seems like SQL refused to use the PK index to seek and was using table scans to locate a PK. Now when I execute the SP manually, it executes super fast and the query plan shows it joining the replication metadata contents to my new nonclustered index [IX_Session_SessionGUID] on the rowguid=SessionGUID seek and is joining the results to the clustered index [PK_Session] seek on SessionGUID=SessionGUID. Not optimal, no idea why I had to do this, but has solved our problem for now.

If anyone reads through this thread, do you have any ideas on why this might occur? Could it be index corruption, something I could look up somewhere?