My suspecion (not seeing the code) is that it potentially has to do with the way the seed sequences for clustering are selected. I think, thought, USearch goes through and compares against the OTUs until it finds one that matches. It may be possible that there’s a better match later, which might explain the difference if the sequence ordering is different different places. But, again, closed algorithm, Im not sure.
As far as vsearch performance, I checked their help page, and didn’t see a stability issue come up. You may want to do a deeper dive there, though. Sorry if this isn’t as direct of an answer as you might like, and more of a new direction.
However, if you’re doing do novo clustering (and it sounds like you are, if your OTUs are unstable?) you might want to consider a subOTU method, if you’re working with 16s. It gives you sequence level resolution, which should be more reproducible and robust than clustering. This (of course) fails whether other de novo methods fail, like cross-hypervariable region comparisons.
Hope this is semi helpful