A problem has been encountered in the Microsoft Exchange Messaging and Collaboration Services setup component. Canceling setup.
After the error message the Exchange 2003 server appeared to continue decommissioning, and when it rebooted Exchange 2003 no longer was listed in Add/Remove programs. However on the Exchange 2010 server when doing a Get-ExchangeServer, the Exchange 2003 server still came up in the list meaning the Exchange 2003 server still existed within Active Directory.
To finish the uninstall manually I deleted the Exchange Server Object in Active Directory with ADSIEdit following the instructions documented under Microsoft KB833396: