I run a server hosting company the currently only uses PayPal and Google Checkout as payment gateways. Both offer minimal fraud protection/verification (I think google is a little more aggressive about it than paypal). I'm considering signing up for MaxMind Credit Card Fraud Detection, but was wondering if there are any (paid) payment processors that include this type of service.
There is - 2checkout. But no matter what fraud screening your payment processor has, you have to do your own manual screening on top of it.
Most payment processing have Fraud protection software in place at the back-end, but you are still responsible for each and every transaction going through so you may want to use services like MaxMind to reduce the number of chargebacks. I don't know about any company who include this in the standard processing fees, it is almost always a fee on top of the regular transaction fee.
I suggest you verify orders by phone using services like OnVerify or MaxMind Telephone Verification. They cut off fraud greatly, since fraudsters tend to go at easier targets.
Checkout Subuno.com, it has a bunch of third party fraud prevention data services integrated, including MaxMind.