If your still having issues, you may want to look into 2checkout. I currently offer paypal express, 2checkout, and check/moneyorder. Only reason I added 2checkout is I have many customers that wont touch Paypal.

2checkout has recently added paypal as a payment option when checking out via 2checkout. In the two tests I have done the correct info is getting transmitted when using a different shipping/billing addresses. The seller only pays the 2checkout fees and not the paypal fees. In fact the seller doesn't even have to have a paypal account.

I would never had even known customers had that option if it weren't for me switching from a osc based cart to zen. It might be a solution to fix your problem.