Attached is the profiler trace for when I executed sp_MSenumchanges_belongtopartition manually, showing it taking 8 minutes. Wait time on the process is zero, task state is running the whole time.

I'm not sure if it's related, but I've noticed another case of SQL using a bad query plan. I have a LogEvent table that's indexed on the [Replicate] bit (no included columns on the index). And if I type:

SELECT MIN([CreatedDate]) FROM [LogEvent] WHERE [Replicate]=1

then SQL takes several minutes to do a full table scan instead of using IX_LogEvent_Replicate.

And if I type

SELECT MIN([CreatedDate]) FROM [LogEvent] WITH(FORCESEEK) WHERE [Replicate]=1

then SQL takes a few ms and returns the min value immediately using IX_LogEvent_Replicate. All of the statistics on the table have been updated, no effect, but I've never tried creating manual statistics.

I did a report on index usage, and most of the tables seem to be full of seeks except the biggest join filter table that seems to be hanging up replication. It's showing 3473 "User Seeks" in the last 3 hours, and 918 "User Scans" on the clustered rowguid index. It's a 20 million record table, so I think the user scans are my problem. It seems to be the only table that's full of user scans, the rest of zero for the most part, or less than 10.

I think I'm getting close to the problem, but I honestly can't see why it would be table scanning when it's a heavily indexed table. None of my other table articles, even ones with the exact same join filter logic and index structures, are doing table scans. Index usage is normal, almost entirely seeks.