Go to control panel and then 'Add remove programs' and see if it is listed. If so use the option to change remove and get rid of it. if not the get CCCleaner (free ware) and use the uninstall option then clean the registry.
By installing Office 2007 in the same directory as your Office 2003 it should overwrite it and leave you with 2007 only.
If you are still having problems and you have the installation program for Office 2003, start trying to install when it starts it will ask you do you want to add features, repair or uninstall, just click uninstall.
Edit: If you formatted your machine it could not be there, what did you do to say you formatted your machine?