You are going to need to put in the debug code for Express Checkout on your pp_checkout_failure page. Here is the code to add to your page:
<?php
echo("PayPal Express Checkout requests and responses :<br />");
echo("Auth request: ".isset($_SESSION['ECO_Auth_Request'])?$_SESSION['ECO_Auth_Request']:""."<br /><br />");
echo("Auth Result: ".isset($_SESSION['"ECO_Auth_Result'])?$_SESSION['ECO_Auth_Result']:""."<br /><br />");
echo("Get Request: ".isset($_SESSION['ECO_Get_Request'])?$_SESSION['ECO_Get_Request']:""."<br /><br />");
echo("Get Result: ".isset($_SESSION['ECO_Get_Result'])?$_SESSION['"ECO_Get_Result']:""."<br /><br />");
echo("Preocess request: ".isset($_SESSION['"ECO_Process_Request'])?$_SESSION['ECO_Process_Request']:""."<br /><br />");
echo("Process Result: ".isset($_SESSION['ECO_Process_Result'])?$_SESSION['ECO_Process_Result']:""."<br /><br />");
?>
Please add this to the pp failure page then test the pages out again. You should get the full information for each of these steps, post back with what you discover.