from your description, I can tell that you are testing using PayPal Express.
For Paypal Express, there are two separate bindings to use depending on where the failure is taking place.
If the failure is taking place when you click the Express check button on the Checkout page, When adding the Failure Response bindings to the bindings panel, select the "authorize Express Checkout" option in the list of gateways. If the failure is happening when clicking the Submit order button on the pp_confirm page, select the "Process Express Checkout" option in the list of gateways.