Domain Rename

We have the old problem of a different outside domain name vs inside name.  It wasnt a problem until we migrated to Exchange2007.  Now we get the nasty certificate error when starting Outlook and the MOC client.  Our environment is small and includes 2 Windows 2003 domain controllers, 2 DNS servers, Exchange 2007, Exchange 2003 (not yet decommissioned and sitting on a domain controller and the global catalog), OCS2007 R2 (not yet deployed), Sharepoint WSS 3.0, SQL 2003&&.  Our inside domain name belongs to another company so we cannot obtain a cert from a commercial CA.  
My questions are:
What are our options besides performing a domain rename operation?
If a rename is the only option can we migrate Exchange users back to 2003 even though the server is on a domain controller?  I understand Exchange 2007 does not support the rename.  What are our options with OCS?  How will this affect other applications  CRM40, Great Plains etc?
We have downloaded the rename tools and documentation and are in the process of creating a test lab.  Still, I read horror stories about the renaming process.