I know there are a lot of haters, but I've had no problem integrating with PayPal's PayFlow Pro. It's not PayPal, it's a regular payment gateway. They bought the business from Verisign a while back.

I'm not involved on the business end so I'm not sure what the rates are, but the API is easy to integrate with and it's stable. Though I guess all gateways can have trouble like a datacenter fire.

Your best bet is probably to have a backup gateway and a non-gateway backup like PayPal or Google Checkout. Cover all your bases.