i have to choose between several payment gateways. I heard that PayPal is quite a mess and there were several fraud-issues? Does some of you have experiences with PayPal?

Thanks in advance

I have.

PayPal is, in my opinion, one of the best gateways around the world, if not the best.

Let me answer straight to your points:

1. "Quite a mess": actually not. PayPal's APIs are widely documented and PayPal offers you a sandbox mode to test your software with fake accounts and fake money to see if your software works or not (you might find, for example, your ecommerce application tries to deliver an order the customer didn't pay for after canceling the order, etc). I don't think this stands for quite a mess since you can perform deep software testing
2. Fraud issues. Let me tell you that Internet frauds occur often, and it's difficult (while not impossible) to protect from them. PayPal does a lot to protect both customers and sellers from frauds. Customers are mainly protected on eBay from fraudulent sellers, but sellers are protected from chargebacks too. If a fraudulent customer buys goods from your website, the chargeback protection applies. In all cases, PayPal might freeze part of your money during investigations.

By the way, PayPal as payment gateway enables your website to accept all credit cards, so you don't need to sign with another gateway.

Unfortunately,

PayPal is expensive IMHO. A little too expensive...