Is Stripe that other provider? I've been contemplating switching but I agree with your sentiment that PayPal's fraud detection is the best available right now.
I'd definitely be interested in seeing a write-up about integrating Stripe with third-party fraud detection systems.
In fact, I often spot fraudulent charges very quickly and have to email my third part processor to refund or cancel the payments.
I was pointed to http://maxmind.com by another HN poster, which is an API that'll give you a probability of a charge being fraudulent so you can verify it before passing it to the payment provider. I'm going to test that out in combination with Stripe.