The solution was surprisingly simple.
I replied to Intel on the email they send me when I build the latest version of my app in their XDK, requesting a copy of my keystore certificate. (Your email to Intel must be send from the address that you registered your XDK with). About 2 days later they responded with a download link for the certificate. Following the steps, I managed to get an exact copy of the certificate issued.
I used this certificate in VS2015, implemented Flurry ads and successfully managed to Cordova build and update my app in Google Play Store. The size of my app is now reduced from 46MB to 19MB, supported apps increased from about 7000 to 9022, and Google is happy with my certificate.