Pff I finally solved it. It turned out that I had to put:
"apiMigrations": {
"signed-install": true
},
In the atlassian-connect.json file!
To be honest, I think this should be clearly defined in the documentation for this. I only found out about this after many hours and eventually found it because of a reference to the concept of API migrations in some Atlassian source code on Bitbucket. If I had not stumbled upon it by accident I could have spent many more hours looking for it.
Now, if you simply follow the documentation you will always run into this issue. There is no mention of this API migration at all in the docs. Even the provided examples do not include it so are technically wrong.
Please put it in the docs!!!