See this article: Orphaned child domain controller information may not be replicated to other Windows 2000 Server-based domain controllers
Problem is almost resolved. Been talking to Microsoft these last two weeks - we are at the last stage of monitoring replication and cleaning up.
And yes, you are right about KB http://support.microsoft.com/kb/887430. It's the first step required to rejoin the orphaned domain to parent. Unfortunately, I didn't get confirmation that this would work with Windows 2008 servers and in Windows 2003 Forest/Domain level installations - if I had, it would have saved a call to Microsoft. :-) AND Microsoft's KB article was updated (APPLIES TO doesn't mention anything other than Windows 2000 Servers!!) See attached image kb887430.jpg
However, the whole process isn't as simple and involves many steps.
OK people, this is for the benefit of the masses.
From watching Microsoft troubleshoot the problem, besides the SOPs they ask you to do, (MPSReport, Network analyser captures, etc), these are the steps and things to take note of if you have a situation such as this.
1. You need to run the commands on the PDC.
2. You need to double-check using regedit even after using the "repadmin /regkey