You might consider trying to solve the problem by moving the risk of loss to another company. That might sound odd, but that is the extra small fee you can pay to ensure the shipper has a valid acknowledgment of delivery, or you get your money from them (insurance).
Since your question is about payment processors, go back to PayPal and everyone else you might want to work with and ask them if using a acknowledged delivery service will help you improve your score. It should. Talk to their risk prevention department and let them know you are interested in reducing the fraud so you can both do better working together.
Depending on location, start by looking at the big shippers, FedEx, UPS, DHL and national postal services. That will give you a baseline of cost if you want to compare further (I prefer to use one of the big ones if at all possible).
Shipping insurance for start-ups is often a great way to distribute your risk across sales, at least until revenue is sufficient to consider self-insuring for the risk of fraud loss. Generally when costing transportation for goods I will "bake in" the cost of insurance. If I can't afford it, I consider my margin too lean for a start-up. I then focus on the margin as the primary problem.
