At the bare minimum, they should
help. They don't. They can't because they don't have the capacity to, but that is no excuse to profit over a platform they themselves have built that is being openly utilized by criminals to scam people, of which they are completely aware, and only doing the bare minimum to continue to stay in business.
As for what could solve the actual problem, there is one solution that always works, and that is insurance. Based on the claims, including false claims (it doesn't really matter), a company can calculate the loss probability, and sell protection. It would be a form of seller protection insurance that would save you from various situations as long as you follow the guidelines.
Of course, mail swap fraud is incredibly stupid because the perp is accepting the package to do their deed, leaving a decent trail of evidence. Mail theft is also stupid because there are harsh laws in place that would make it so not worth it compared to other forms of theft. So both are fairly rare. But they do happen because there are no shortage of idiots.
Since filing a false police report is in itself a crime, the honest innocent victims should all be filing more police reports, and PayPal and eBay should act based on these. So if someone returned a brick, you could file a report, have PayPal confirm it, and get your money back. Everyone should help you along this process, and it should be made simple and fairly easy. They don't, and it isn't.
And if you're a victim of a false police report, then you should be compensated even more for your troubles. If we have red light cameras that automatically send us fines, there is no reason we couldn't build a system for transaction fraud that would automate much of the violations involved in commerce. The credit card chargeback system is an example of one such system which are all maintained by corporations for their users. I'd opt for a public one for the people.