You're going to have issues with any payment plan you've got. Paypal is good, as others have said, if you give them a call and talk to a representative directly. I've been using Paypal for years, and yes, I have had my downsides to them, but a large sum of clients/potential clients are using Paypal and without the option of paying, you'll be losing a large sum of clients.
I'd recommend getting a good friend at Paypal (be friendly with a certain rep) and once you've got one that will help you with your issues, life will be much easier. In the hosting industry you're going to lose and keep money, that's an obvious fact. Sometimes you're going to lose more than other with one payment, the key is, to look at how much money/clients are actually coming from that payment option. I personally wouldn't go without Paypal unless it was critical.