(The following applies for all versions of FFX except the original Japanese version.)
The Bribe minimum is actually {MaxHP * 325 / 64}. At that amount, you only get 1/16th of the items listed in the guides (minimum 1), and the chance of success is 1/256. Even though Bribes are cumulative (if a Bribe misses, you can Bribe again for 1 Gil and the previous Bribe amount is added in with it), it typically takes a long time to get it to work for that low (expect 30 minutes even with a turbo setup), so I don't recommend it.
The optimal cost-effective Bribe amount (strictly in terms of Gil) is 10 times the monster's Max HP. You get about half the prize quantity listed in the guides for 40% of the base price. (Why 40%? See below!) Also, the success rate is an acceptable 25%.
With a successful Bribe at 20 times the monster's Max HP, you average slightly less than the amount of items listed in guides (about 87% of the quantity). This is because Square raised the base Bribe prices in the North American and later versions of FFX, a change that none of the guides documented (save for FFX Ultimania Omega, which was published by Square's now-defunct subsidiary, Digicube). Even so, there's nothing bad about this amount (but nothing all that special about it either). Success rate here is 75%.
The base Bribe price (at which you will average the prize quantities listed in various FAQs and guides) is 25 times the monster's max HP. The good thing about this amount (and higher amounts) is that Bribes will always succeed. However, this is almost irrelevant because there is no real penalty for a Bribe miss (besides having to wait for another turn). Another reason not to bother with Bribing this high is that you get more items for your money at lower amounts. If you can deal with sitting through a few misses, you will save Gil in the long run by Bribing at 10x (or lower for monsters that give 1 or 2 items like Maelspike or Chimera Brain).
I just typed this out, so please forgive me if it's not entirely coherent.
