I never found a proper solution per se. All I did was remove my WinXP SP3 VM from the domain then rejoined it. All subsequent linked clone deployments were successful, ie joined the domain fine.

I have some theories on why the original deployment didn't work but I don't have time right now to test those out so I used the above method to get over that hurdle. It may be the only fix and in reality, how hard/quick is it to do a remove/add to domain? Not very!