After reading Joel Olesen's blog and the Microsoft kb on how to delete orphans in Sharepoint 2003 a supported way, I was excited to try it out. I requested the hotfix from Microsoft support and tried to install it in my test SPS 2003 environment - which is not a true representation of production but helps out in some ways regardless. After unzipping the neccessary files, I was left with a STS.msp file. When I tried to run that, I got a screen which said that gave me 2 options - Uninstall WSS 2.0 or repair and reinstall it. This would not fly in production - I did a quick test to find out if I would in fact get the same screen and I did. So I exchanged a few emails with Microsoft support and was told that this was an anamoly in my environments and this works in other environments. So basically I abandoned the approach of trying to delete our orphans and potentially bring down our SPS 2003 environment in the process of doing so.
We will live with the orphans and deal with them after the migration to MOSS 2007.