I have used PayPal for about 10 years now, and process six figures with them per year. I also have merchant accounts and other 3rd party payment system integrations, but there's no reason to exclude PayPal based on fears of future problems. With over 90 million active accounts, the occasional problem you read about isn't unexpected or more extreme than you'd get processing anywhere else.

Regarding Recurly, my opinion of that company is much lower, but maybe I am one of the few with a bad experience: http://news.ycombinator.com/item?id=1678143