Paypal is great as a backup payment system. However it's trigger happy shutdown procedures make it a horrible single point of failure.

You sound like you're at the critical mass where you should be able to use a payment gateway. You should offer both as a mechanism, then if paypal tosses you out, you're set.