I figured out what was causing this issue.
I used Wireshark to determine if a call to the LDAP server was even going out in the first place and it turned out that it wasn't. It was if I was using openldap's ldapsearch utility. Which indicated that Moodle's call to the LDAP server wasn't going through.
I then checked any outgoing firewall rules on this box (using firewall-cmd) and that indicated there were none that would block it.
The last thing left to check was SELinux and sure enough it was running and it had a restriction that prevented the outgoing LDAP request. I proved it by temporarily disabling SELinux (setenforce Permissive). The LDAP request went through and and authentication worked!
I am in the process of determining the exact SELinux rule to open up for such requests to go through.
Hopefully this helps others.