Ok, I think I found the rounding bug inside the paypal gateway's handling of tax. The way that it computes the amount to pay in case there is tax makes it fail in some particular cases.

(btw, putting "!!!" and "???" emotional markup inside your precise and factual analysis (thank you for the analysis) doesn't help understanding the explanation).

Bug is marked as #3120 and will be fixed in upcoming CB 1.3.0. If you are interested to test a beta version, please private-message me with URL to this thread and your email.

Quick update: this bug #3120 is now fixed and i'll email you a build to test tomorrow.