Cure: Use Windows registry editor as follows:-
1. Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Bethesda Softworks
2. Delete the Oblivion subkey (looks like a folder)
Setup checks for the existence of the Oblivion subkey (or one of the subkeys or values under it) to determine whether Oblivion is already installed. The uninstall should have removed it. If not, deleting it should fool Setup into allowing you to install Oblivion again.
When you install a program, you run its Setup utility, which creates new Windows registry entries, folders and files. It also creates a "uninstall" log file somewhere on your machine which contains a list of everything Setup created, in the order it created them. When you run the program's uninstall procedure, it simply goes through the uninstall log in reverse order, deleting everything. However, if new files have been created in the folders SINCE Setup was run, they're not deleted and, if folders still contain files, those folders are not deleted.
The reason the Oblivion folder wasn't deleted is that many of the files in there didn't match the ones in the uninstall log (because afterwards, you patched Oblivion and installed utilities, mods, etc, i.e. MORE new folders/files). This is INTENTIONAL behaviour, to ensure that you can uninstall Oblivion (if corrupt) then reinstall/patch it and still have all mods and their files as intact as possible. That way, Oblivion should pick up your mods again the first time it runs. It doesn't work in every case, but at least it avoids you reinstalling ALL mods from scratch every time.
As long as Oblivion uninstall has run OK (and deleted what it can, including the Windows registry entries), it's safe to delete the Oblivion folder to complete the uninstallation manually.
You should ONLY ever use a 3rd party uninstaller to delete leftover traces of a program if you NEVER intend to reinstall that program again. After all, if you're reinstalling, Setup will overwrite existing traces anyway, so why bother deleting them only to have Setup simply recreate them again?