This work investigates the coalescence of water droplets settled on a water-oil interface in the presence of microparticles and surfactant. The successive stages of the coalescence process, including interstitial film formation, drainage, rupture, and retraction, are analyzed in detail. This leads us to distinguish between contrasted situations depending on the nature of the surfactant and its affinity with the microparticles. Hydrophilic particles have been previously shown to promote coalescence by means of a bridging mechanism. In that case, coalescence is a deterministic process that lasts the time required for the drainage to make the film thickness equal to the size of the particles. However, the present study shows how surfactants can totally change the effect of the particles upon coalescence. When surfactant both stabilizes the water-oil interface and adsorbs onto the particles, the bridging mechanism is inhibited and the coalescence becomes a random process. Since molecular forces between facing film interfaces are not attractive, thermal fluctuations are required to initiate the formation of a hole in the adsorbed surfactant layer. Provided the surfactant concentration in the bulk is large enough to ensure that the interfaces are close to saturation, the coalescence is delayed by a stochastic time interval and the drop coalescence becomes a Poisson process. These results shed a new light on the mechanisms of droplet coalescence in complex industrial applications where surfactant and particles are present, either purposely added or present as uncontrolled contaminants.