No Netlogon or SYSVOL & GC Unavailable

Make sure your current DC has all the FSMO roles (this is because it sounds like you only have 1 DC).  To do so run netdom query fsmo.  If any are on a failed DC look into seizing the roles here - http://support.microsoft.com/kb/255504.  It sounds like your PDC Emulator might not be working.

I would also run DCDiag /Fix and NetDiag /Fix to try to re-register all the needed services and such.

Brian

Ok so right now you have 1 server and are trying to join a second server -

OK the machine  you brought down did it hold all the fsmo roles?
If so you will need to seize the fsmo roles from the down machine to the existing machine left.
http://support.microsoft.com/kb/255504
Now wipe the machine from AD using metadata clean up
http://technet.microsoft.com/en-us/library/cc736378.aspx

Now the machine you took down can not come back to the domain without wiping it.
Now the existing machine should hold all the roles and be a global catalog.  Verify it holds all the fsmo roles
from a command prompt
DCdiag /test:Knowsofroleholders /v
If the remaining machine is a win2k machine you will need to run adprep /forest prep form the win2k3 cd (run the command on th win2k machine - this preps AD for the win2k3 server)
Once thats all you should be good to add the server to the domain

All the FSMO rolls are currently held by the remaining DC and I have run DCDiag /Fix and NetDiag /Fix several times to no avail.

I got this error in the system log too:

The Netlogon service could not create server share C:\WINNT\SYSVOL\sysvol\domain.local\SCRIPTS.  The following error occurred:
The system cannot find the file specified.

the only thing that dcdaig now seems to throw up is:

      Starting test: NetLogons
         Unable to connect to the NETLOGON share! (\\SERVER\netlogon)
         [SERVER] An net use or LsaPolicy operation failed with error 1203, Win3
2 Error 1203.

The GC issue seems to have been resolved by some of my earlier efforts.

I had already cleaned up the metadata sucessfully...

You can try to rebuild the SYSVOL with the burflag method. If you forced remove a DC then you need to do a metadata cleanup then try the burflag method.
http://www.petri.co.il/delete_failed_dcs_from_ad.htm

http://support.microsoft.com/kb/315457/

I shoudl mention that this was originally a Windows 2000 Server that was upgraded to Windows Server 2003 STD....

Is the BurFlag key different in that case?

No its fine

I'm working through that guide, however I don't thve the LINKD command, where do i find this?

Still no NETLOGON either.

Also now getting various errors in the event log, however it is looking more promising!

Event Type:      Error
Event Source:      NETLOGON
Event Category:      None
Event ID:      5706
Date:            10/12/2008
Time:            21:31:27
User:            N/A
Computer:      SERVER
Description:
The Netlogon service could not create server share C:\WINNT\SYSVOL\sysvol\rvsl.local\SCRIPTS.  The following error occurred:
The system cannot find the file specified.

-------------------------------------------------------------------------------------------

Event Type:      Error
Event Source:      Userenv
Event Category:      None
Event ID:      1030
Date:            10/12/2008
Time:            21:37:32
User:            NT AUTHORITY\SYSTEM
Computer:      SERVER
Description:
Windows cannot query for the list of Group Policy objects. Check the event log for possible messages previously logged by the policy engine that describes the reason for this.

----------------------------------------------------------------------------------------.

Event Type:      Error
Event Source:      MSExchangeAL
Event Category:      LDAP Operations
Event ID:      8026
Date:            10/12/2008
Time:            21:19:15
User:            N/A
Computer:      SERVER
Description:
LDAP Bind was unsuccessful on directory server.rvsl.local for distinguished name ''. Directory returned error:[0x34] Unavailable.    

I have nothing at all in the SYSVOL folder collection... the folders are now all present and correct, but they are all empty, that's not right is it? Shouldn't there be GPOs in them?

No it builds them empty you will need to do a restore to get the GP's back or recreate them if they were small

Right.... good, there was very little specified in them, how would I go about re-creating them in the simplest possible way?

You would need to create the gpo's from the gpmc console

Before you embark on recreating ... mak eusre that all is well and replication is happening and no errors are showing in event log

ok, I'm still getting this in the event log, does this mean the GPOs are not orphaned? will this go when I re-create them?

Event Type:      Error
Event Source:      Userenv
Event Category:      None
Event ID:      1058
Date:            10/12/2008
Time:            23:16:50
User:            NT AUTHORITY\SYSTEM
Computer:      SERVER
Description:
Windows cannot access the file gpt.ini for GPO CN={6AC1786C-016F-11D2-945F-00C04fB984F9},CN=Policies,CN=System,DC=rvsl,DC=local. The file must be present at the location <\\rvsl.local\sysvol\rvsl.local\Policies\{6AC1786C-016F-11D2-945F-00C04fB984F9}\gpt.ini>. (The system cannot find the path specified. ). Group Policy processing aborted.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

Is this still an issue?  Thats referring to a policy that is no longer there