PayPal isn't really that bad. Most of the horror stories are from people breaking the terms of service (donations without getting approval, long preorders etc). Wikileaks was blocked by MasterCard.
We've been in PayPals sights a few times (we had a site bug once that double-charged a bunch of customers, and charged one customer 28 times! We had to do over 1000 chargebacks.) We got a massive rolling hold but the whole time PayPal were willing to talk to us. We've even won some customer card chargeback disputes on digital goods through PayPal.
For a short while we switched to a traditional merchant account but that was hell from day one. Aside from the paperwork to get set up, they hated the fact that 40% of our sales were outside the U.S., that our sales are highly seasonal, etc.
That said, to someone starting today, I'd still probably recommend Stripe instead.