I found out there is an alternative way to fix the “Trust Relationship Between Workstation and Domain Fails” issue without rejoining the domain.
You can read all about it here.
netdom.exe resetpwd /s:<server> /ud:<user> /pd:*
<server> = a domain controller in the joined domain
<user> = DOMAIN\User format with rights to change the computer password
For all details, check the link above.