I guess you got all bases covered 🙂

The only thing I can think of then (before an MS Support call!) is contention with all your Agent Jobs. Together with the Cleanup jobs that's a lot of connections hitting the same tables in your Distribution database (Have you checked disk waits or any other?). I have found Reorganizing the Indexes on the Distribution database in heavily replicated environments does help with performance as they do get fragmented, but I only do this with custom code that first checks how many commands are queued for replication and does the Reorg at a time of low replication activity.

I hope your server tracing or verbose logging picks up the cause of the issue. Would be interesting to know what it was when you eventually identify it.