Certificates not being updated even after domain deletion / creation for custom CNAME

Summary

For one of my Gitlab pages, yesterday's certificate (from StartSSL which was insecure) is being served even after I delete the custom domain both from Gitlab and from the DNS records, and then re-create with the correct settings and a new certificate (from Let's Encrypt).

Steps to reproduce

1. Create Gitlab page
2. Add custom CNAME along with certificate copy/paste (I hope this step can be automated in the future...)
3. Everything works, but I don't like the current certificate so I decide to update it
4. Delete custom CNAME
5. Re-add custom CNAME and paste new certificate

Expected behavior

Certificate should be updated as soon as the domain is re-added.

Actual behavior

Not only the new certificate is not being served, but the old certificate is still being shown after several hours of updating to the new certs!