My Default Domain Policy Group Policy Object (GPO) shows Add workstation to the domain right as disabled. However, I was able to add a workstation to my domain with a regular user account. What gives?

First you need to check the Default Domain Controller Policy GPO which, for domain controllers (DCs), takes precedence over the Default Domain Policy GPO. DCs are where this right is enforced.

Second, users can also gain the authority to create computers in the domain through the Create Computer permission. Check the permissions on the root of your domain and its organizational units (OUs) to see whether Create Computer is currently granted to Everyone, Authenticated Users, Domain Users, or a similar broad group.