Sue Paypal. It's an obvious scam, and they are, for some strange reason, ruling in favor of the scammer.

Sue them for your money, for the time you spent dealing with them. Check out small claims court limits in your state, and sue them for the maximum.

I bet you will win with all the documentation you have.