Put it in the Computer Configuration Startup.
Create a FIX_TRUST.cmd and put this in it:
================================================================================
CALL :GO>>"C:\FIX_TRUST.log" 2>&1
:GO
NLTEST /SC_VERIFY:<fqdn of domain> | FIND /I "ERROR_ACCESS_DENIED"
IF %ERRORLEVEL%==0 GOTO FIXTRUST
GOTO END
:FIXTRUST
netdom resetpwd /s:<fqdn of domain> /ud:<NETBIOS DOMAIN NAME>\<useraccount> /pd:<password>
:END
exit
=================================================================
With this in place.. at every startup of the Virtual Machine it will check if its still trusted by the domain.. IF NOT.. It will reset and resync the machine account passwords between machine and domain controller(s) and VOILA everything works!