Henchmen Multiple Employers

I understand that there are only 1d2 potential 0-level henchmen in a class VI market. My question is, if they turn down the dwarf, can the cleric try the same henchmen? And failing that, the mage? And so on in that manner until the henchmen are all hired or everybody has turned them off?

Or are they soured on the party (or perhaps just adventuring) as a whole?

We’ve been playing it such that in general each PC can attempt to hire a given hench until one succeeds or they all fail (unless someone gets the slander result, in which case perhaps not).

That is the correct way to do it!