Just had time to troubleshoot this further.
So the problem isn't really it just automagically choosing another certificate in the list, it is due to certificate renewal in combination with auto-connect.
In the list, most if not all clients have at least two certificates to choose from, but the client has since long cached the certificate to use when auto-connecting.
What we saw, was when I renewed the certificate, and immediately rebooted my computer, we received the error that it was unable to find a valid certificate during auto connect.
I'm just assuming here, but I suppose it is looking for the old certificate prior to the renewal, and doesn't find the new one properly.
Is there a workaround to this? Working as intended? Newer version has a fix?
Thanks again.