If you get the error code 0X80072030 (8240) when trying to uninstall an exchange 2003 you have to take a look in the log file (c:\Exchange Server Setup Progress.log). Scroll down to the end, where the uninstall failed and watch for the "Creating Ldob from" right before the error. The line should contain a LDAP path to an object wich couldn't be found. Simple solution, open adsiedit.mmc and create the object.
In my case the uninstall failed again and again with more different kind of errors, e.g. i had to give him the mapi32.dll and pttrace.dll again (just copied it to system32 from the old sp2-setup).