It seems like a large number of security groups have been deleted from the organization's AD.
I was able to find the tombstones but I see there 1400 objects from the last 180 days and I know for certain that the important groups which have been deleted, have been deleted somewhere between last night and now.
Is there a way, maybe by using PowerShell, to extract the names of all objects which have been deleted throughout the night?
For your 2003 domain, use a tool such as Softerra's LDAP Administrator to view and recover deleted items from Active Directory.
You would need a Windows Server 2008 or newer domain controller in order to use PowerShell for that query. Raising the domain functional level to 2008 also allows you to turn on a new Active Directory Recycle Bin feature.
read the following links.
http://technet.microsoft.com/en-us/library/cc978013.aspx
http://www.petri.co.il/manually-undeleting-objects-windows-active-directory-ad.htm
and yes this all could be done with powershell, unfortuantely I'm not at work so I can't test any powershell commands that I would use.