Lenny,
Your understanding is correct.
In order to perform the domain rename you’d need Windows Server 2003 and Exchange Server 2003. Windows did not support domain rename until Windows 2003, and if you were to upgrade to Windows Server 2008 you would not be able to install Exchange 2003, which is the only version of Exchange in which you can use the Exchange Domain Rename Fix-up Tool.
So yes, if you wanted to rename the domain you’d need to install Windows Server 2003 and Exchange Server 2003, and then rename the domain. At this point however, if you wanted to further upgrade the operating system to Windows Server 2008 you’d need to remove Exchange Server 2003 since Operating System in-place upgrades of Exchange Servers are not supported (see http://msexchangeteam.com/archive/2007/10/04/447188.aspx for more information).
Your alternative is to build a new FQDN domain parallel to the existing SLD and then migrate users.