I have joined this forum after googling exactly the same problem. Two days ago, PayPal suddenly blocked access from my server IP address, with no warning or explanation. I have made no changes to my site in months. A simple curl command to https://api-3t.paypal.com/nvp from a shell fails with a 'couldn't connect to host' and all API requests timeout.
Like the rest of you, I found first and second-line support to be fairly useless. I have now sent an email to the MTS team, after finding they exist, but am not particularly hopeful of a speedy resolution.
I think I am going to hit twitter with this is well and try and shame them into some action.