Thanks a lot for the reply. We are working on the issue right now. We were able to narrow-down the problem to locks between SQL agent and distribution cleanup job or history cleanup job. We've disabled the jobs for now and researching what are optimal parameters and frequency for them.