I managed to get it working with a FREE certificate from startcom.org (heard about on Security Now Podcast).
Their website is horrible, but PayPal seems to be OK with their certificate where they aren't OK with a Godaddy certificate - both 4096 bits. Plus it's free :-) Although only good for a year.
As soon as I switched to this certificate it worked fine.
It was definitely something unacceptable to PayPal about the GoDadaddy/Starfield issued certificate.
There is also a service ngrok which I found very useful to allow me to test locally. It allows you to set up a tunneling proxy that is accessible from the outside. Even without touching firewall settings you can create an address like http://83def5f1.ngrok.io that is accessible by PayPal and redirects traffic to your local machine allowing you to set breakpoints.
Proxy page
(Completely unrelated to ngrok)
I preferred not to use this certificate for my live sites (plus I have several different sites on UCC certificates I didn't want to change), so I made a proxy page that redirects the request to the right server. I then just send the following to PayPal
"https://example.com/paypalproxy.aspx?callbackUrl=" + HttpUtility.UrlEncode(callbackUrl)
(Where callbackUrl is your regular callback URL that you would send to PayPal)
The proxy is an ASPX page - it doesn't need to be compiled just put into a .NET IIS website.
You can check to see the last request/response calling it with ?debug=Y
<%@ Page language="c#" AutoEventWireup="true" %>
<%@ Import Namespace="System.IO"%>
<Script runat="server" language="C#">
private static string _lastURL;
private static string _lastRequest = "";
private static string _lastResponse = "";
private static DateTime? _lastTime;
private static int _lastDurationMs;
    private void Page_Load(object sender, System.EventArgs e)
    {
        // no cache
        Response.Cache.SetCacheability(HttpCacheability.NoCache);
            var sw = new System.Diagnostics.Stopwatch();
            var wc = new System.Net.WebClient();
            sw.Start();
            var callbackUrl = Request.Params["callbackUrl"];
            var debugMode = Request.Params["debug"] == "Y";
            if (debugMode) 
            {
               Response.ContentType = "text/text";
               Response.Write(_lastTime + "\n");
               Response.Write("LastURL = ["+_lastURL+"]\n\n");
               Response.Write("LastDuration = [" + _lastDurationMs +"]\n\n");
               Response.Write("REQUEST: \n[\n  "+_lastRequest.Replace("&", "&\n  ")+"\n]\n\n");
               Response.Write("RESPONSE: \n[\n  "+_lastResponse.Replace("&", "&\n  ")+"\n]");
               Response.End();
           return;
            }
            _lastDurationMs = -1;
        _lastURL = Request.Params["callbackUrl"];
            _lastTime = DateTime.Now;
            if (callbackUrl.Contains("dev."))
            {
                throw new ApplicationException("Callback shouldn't be to a dev machine!");
            }
                        
            if (callbackUrl.Contains("https") == false)
            {
                throw new ApplicationException("Callback must be https");
            }
            
            var newUri = callbackUrl + "?" + Request.Form.ToString();
            var str = wc.DownloadString(newUri);
            _lastRequest = Request.Form.ToString();
            _lastResponse = str;
            _lastDurationMs = (int)sw.ElapsedMilliseconds;
            Response.Write(str);
            Response.End();
    }
</Script>