Fixed this issue by disconnecting/uninstalling azcmagent on the machine. What I missed in the beginning - after disconnecting from the machine, Azure Arc resource has to be deleted from Azure (this doesn't delete the server, just the Azure Arc resource for the server), otherwise trying to connect will fail with "resource already exists in Azure". Once the Azure resource was deleted, we were able to connect the machine again.
(not sure why the certificate expired in the first place, will keep an eye on it and if it happens again, will investigate deeper)