so i bought the firelink-tower key early in the game to grab the firekeeper-soul... but no patches who trapped me at the gate there.
i wanted to get him as a merchant asap to buy some rusty coins.
i´ve started to progress further and everytime ive triggered an event, i went back to the tower to see if patches is there.
killed vordt, grotten-tree boss, demon on the bridge, abyss watchers, sage-mage, .... still no patches.
after i´ve lit the "cleansing chapel" bonfire, patches appeared at the tower.
you can even hear the "locked-door-sound" when you take the elevator to the upper platform where the firelink soul used to be.
so im pretty sure that visiting the cathedral of the deep is the trigger for patches first event.