Of course you can simply pay Yojimbo a lot of money and hope for Zanmato, I just posted the information for anybody that's interested.

I raised my Yojimbo's compatibility to 255 and only have to pay him around 10,000 or so gil (could probably pay a lot less but I just like that number, he actually only recognizes powers of 2) to nearly guarantee Zanmato even against fiends with a high resistence level such as Nemesis or the Dark Aeons. 1 out of 4 times he does it for free.