This really has the look of a certificate issue. You stated your firmware was version 36.72.23.3. Per Yealink, for Lets Encrypt certificates, you need to be on at least
36.80.0.95. Download link for that firmware is here:
http://download.support.yealink.com...dde-446f-8ac6-6a3127f2a4a6/T41-36.80.0.95.zip
I would recommend a factory reset, update the firmware, then try again. If that doesn't work, see below for additional ideas.
I noticed you tried the username/password provisioning method. Try this instead:
1) In the 3cx admin interface, obtain the provisioning URL from the phones provisioning page (right under "IP Phone" for the Yealink). It should be of the form https://<FQDN>/provisioning/<alphanumeric string>
2) Log in to the web interface after a factory reset as admin/admin
3) Settings (top tab) and then auto provision (left side menu)
4) Paste the provisioning URL from above https://<FQDN>/provisioning/<alphanumeric string> into the server URL on this page
5) Click "confirm" at the bottom
6) Finally, click "auto provision" just above the confirm button
See if it will provision properly for you this way. Other troubleshooting steps I take when having issues like this are to try a new extension, temporarily disabling all firewall rules during the test provision, and verification the firmware on the phone is the correct version for support by 3cx.