That is pretty common and is down to some barely acceptable code (in my opinion) in the clean up procs. In many cases some of this code isn't even required. I've seen the same job issues many times over, in many environments.

I resolved the deadlock issues in my environment by creating my own versions of the MS procs. It's generally not a problem with distribution database itself.