I finally solved it - here is the story:

When I bought the certificate, I had to collect it by navigating to a website address that I received by email. There, the certificate was automatically installed into the truststore of my browser (Firefox).

I then exported it from Firefox (Options - Advanced - View Certificates - Your Certificates - Backup button).

What I didn't realize at the time was that Firefox, unlike Java and Windows, has the "COMODO RSA Certification Authority" as an inbuilt token:

What I also didn't know at the time was that the Firefox certificate export seems to only include the certificate chain up to the first trusted authority, in this case the "COMODO RSA Certification Authority".

From this COMODO support site I learned that the chain should actually go one higher, all the way up to "AddTrust External CA Root":

That sounded much more promising, because the AddTrust certificate is actually included in Oracle's java 8 cacerts truststore, which is responsible for verifying the jar during java webstart.

The next thing I did was import the *.p12 file I got from Firefox into the windows certificate manager (Start - certmgr.msc), because for some reason I thought this was the way to convert *.p12 to *.pfx (although now I know that both extension are used for the same pkcs12 keystore format). Anyway, during the import this question popped up:

Here I made the critical mistake: I clicked yes. This caused the "COMODO RSA Certification Authority" to be installed in the Windows truststore as a "Trusted Root Certificate" (btw only visible after I restarted certmgr.msc):

My code signing certificate was installed in "Personal/Certificates". I exported it from there (Action - All tasks - Export...), and marked "Include all certificates in the certification path if possible".

Now the exact same thing happened as when I exported from Firefox. Since Windows now had "COMODO RSA Certification Authority" installed as a trusted root certificate, it only included the chain up to this one. This is what I got after the export:

And now for the genius move, which I stumbled upon by pure chance: I deleted the "COMODO RSA Certification Authority" from the Windows certification manager. Now, when I double clicked my code signing certificate, the displayed chain suddenly looked different:

I admit I got a small adrenaline rush when I saw this. I exported again (exact same settings as before).

And indeed, after I signed my application with this exported certificate, java webstart accepts it: