I figured out the cause for the problem, and in case anyone else has the same issue I'll post it here: The problem was something called an Identity Preference that you can create in Keychain Access. To simplify things basically it can be used as an alias where a specific identity name will point to a specific certificate. And it turns out that when codesign selects an identity based on a name it will first look for matching identity preferences. This can be useful (I think this was my case) where you have two valid certificates with the same name. In this case using the name will not be possible in codesign as it will find both and not know which one to pick. So you can create an identity preference with the certificate name and point it to the certificate you want to use. This is likely what I did a couple of year ago. The problem is that these identity preferences persist even when the certificate they point to become invalid or are removed from the keychain. So like described above the certificate name will become unusable and not update if you renew your certificates. To complicate things these identity preferences are not easy to find as they're not shown in the certificate list, or in any other separate list to indicate they exist. But once I figured out this might be the issue I was able to use the search feature in Keychain Access to search the all items tab using the certificate name and found that there was indeed an identity preference there with the same name that I could then remove. It would have saved a lot of work if Keychain Access more clearly showed these identity preferences existed, or even better removed or did not use ones that pointed to removed certificates.

While not quite resolved yet. I've narrowed this down a little to be due to some missing keys in the info.plist of the bundle. It seems that XCode adds a bunch of keys starting with DT* (like DTPlatformBuild, DTXcodeBuild, DTSDKBuild etc) and these are missing since the bundle was not created by XCode App Store Connect thinks they're invalid, which it seems to interpret as being a beta version of XCode. It's however still unclear to me exactly what DT* keys are needed and what they should contain.