Cannot connect to PayPal API via cURL

I'm trying to set up PayPal Express Payment via the "Classic" NVP API.

Trying to connect from my server to the PayPal-Sandbox using cURL, the connection stalls and times out after about 2 minutes.

I'm using the example call from the docs:

curl -v --insecure  https://api-3t.sandbox.paypal.com/nvp  -d  "USER=platfo_1255077030_biz_api1.gmail.com&PWD=1255077037&SIGNATURE=Abg0gYcQyxQvnf2HDJkKtA-p6pqhA1k-KTYE0Gcy1diujFio4io5Vqjf&METHOD=SetExpressCheckout&VERSION=78&PAYMENTREQUEST_0_PAYMENTACTION=SALE&PAYMENTREQUEST_0_AMT=19&PAYMENTREQUEST_0_CURRENCYCODE=USD&cancelUrl=http://www.yourdomain.com/cancel.html&returnUrl=http://www.yourdomain.com/success.html"

Shell output is:

* About to connect() to api-3t.sandbox.paypal.com port 443 (#0)
* Trying 173.0.82.83... Connection timed out
* couldn't connect to host
* Closing connection #0
curl: (7) couldn't connect to host

When I try to do this via PHP curl I don't get any errors and simply an empty resource handle.

I can easily do the requests (and get the correct data back) from my local machine and from other servers that I can access so I guess this is some server side misconfiguration going on. Not being a server person I am a little clueless.

cURL is enabled and logs the following in phpinfo:

libcurl/7.21.0 OpenSSL/0.9.8o zlib/1.2.3.4 libidn/1.15 libssh2/1.2.6

openSSL is enabled as well. Also, I'm having the same issues when trying to connect to the live version of the API.

Try

$ch = curl_init();
# Merchant Account Credentials
$ppUserID = "User Id Email"; //Take it from sandbox dashboard for test mode or take it from paypal.com account in production mode, help: https://developer.paypal.com/docs/classic/api/apiCredentials/
$ppPass = "User Pass"; //Take it from sandbox dashboard for test mode or take it from paypal.com account in production mode, help: https://developer.paypal.com/docs/classic/api/apiCredentials/
$ppSign = "Paypal Sign"; //Take it from sandbox dashboard for test mode or take it from paypal.com account in production mode, help: https://developer.paypal.com/docs/classic/api/apiCredentials/

$ppAppID = "APP-80W284485P519543T"; //if it is sandbox then app id is always: APP-80W284485P519543T

$paypal_header_options = array();
    $paypal_header_options[] = "X-PAYPAL-SECURITY-USERID: $ppUserID";
    $paypal_header_options[] = "X-PAYPAL-SECURITY-PASSWORD: $ppPass";
    $paypal_header_options[] = "X-PAYPAL-SECURITY-SIGNATURE: $ppSign";
    $paypal_header_options[] = "X-PAYPAL-REQUEST-DATA-FORMAT: NV";
    $paypal_header_options[] = "X-PAYPAL-RESPONSE-DATA-FORMAT: NV";
    $paypal_header_options[] = "X-PAYPAL-APPLICATION-ID: $ppAppID";

$URL = 'https://api-3t.sandbox.paypal.com/nvp'
    .'?USER='.$ppUserID
    .'&PWD='.$ppPass
.'&SIGNATURE='.$ppSign
    .'&METHOD=SetExpressCheckout' 
    .'&VERSION=93'
    .'&RETURNURL=https://localhost/express-checkout-single-product/success.php?success=true'
    .'&CANCELURL=https://localhost/express-checkout-single-product/index.php'
.'&PAYMENTREQUEST_0_CURRENCYCODE=USD'
.'&PAYMENTREQUEST_0_AMT=250.00'    #The payment amount for the first receiver   # Merchant(Primary AC) Account Amount
.'&PAYMENTREQUEST_0_ITEMAMT=225.00'                         # Merchant(Primary AC) Account Email
.'&PAYMENTREQUEST_0_TAXAMT=25.00'    #Receiver designation (there can be only 1 primary receiver)
.'&PAYMENTREQUEST_0_PAYMENTACTION=Order' 
.'&PAYMENTREQUEST_0_SELLERPAYPALACCOUNTID=email' 
.'&PAYMENTREQUEST_0_PAYMENTREQUESTID=CART110-PAYMENT0'    #The payment amount for the second receiver   # Seller(Secondry AC) Account Amount
.'&PAYMENTREQUEST_1_CURRENCYCODE=USD'
.'&PAYMENTREQUEST_1_AMT=75.00'    #The payment amount for the first receiver    # Merchant(Primary AC) Account Amount
.'&PAYMENTREQUEST_1_ITEMAMT=65.00'                          # Merchant(Primary AC) Account Email
.'&PAYMENTREQUEST_1_TAXAMT=10.00'    #Receiver designation (there can be only 1 primary receiver)
.'&PAYMENTREQUEST_1_PAYMENTACTION=Order' 
.'&PAYMENTREQUEST_1_SELLERPAYPALACCOUNTID=email' 
.'&PAYMENTREQUEST_1_PAYMENTREQUESTID=CART110-PAYMENT1' 
    .'&L_PAYMENTREQUEST_0_NAME0=Departs2'
    .'&L_PAYMENTREQUEST_0_NAME0=Sunset'
.'&L_PAYMENTREQUEST_0_QTY0=1'
    .'&L_PAYMENTREQUEST_0_AMT0=125'
    .'&L_PAYMENTREQUEST_0_TAXAMT0=15'
    .'&L_PAYMENTREQUEST_0_NAME1=Departs'
.'&L_PAYMENTREQUEST_0_QTY1=1'
    .'&L_PAYMENTREQUEST_0_AMT1=100.00'
    .'&L_PAYMENTREQUEST_0_TAXAMT1=10.00';
    curl_setopt($ch, CURLOPT_URL, $URL);
    curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
  //  curl_setopt($ch, CURLOPT_HTTPHEADER, $paypal_header_options);
    curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false);

    $paypal_response = curl_exec($ch);

$responseAr = explode('&', $paypal_response);
$parsedResponseAr = array();
foreach($responseAr as $i => $value) {
    $tmpAr = explode('=', $value);
    if(!empty($tmpAr))
        $parsedResponseAr[strtoupper($tmpAr[0])] = urldecode($tmpAr[1]);
}
print_r(json_encode($parsedResponseAr));
curl_close($ch);