If you can not find any reference to LabVIEW in the Add/Remove Programs utility, then you will defnitely need to go through and remove the registries. However, you definitely want to make a back-up first... just in case. Open up regedit and select Registry>>Export Registry File... Now give this a name and it will save a backup for you just in case something goes wrong.
Then do just as LabVIEWguru said and remove references to LabVIEW. The first place to look is HKEY_LOCAL_MACHINE>>SOFTWARE>>Nationa Instruments>>LabVIEW. Make sure those are gone and then try installation again. If it still doesn't work, let me know because there's a last resort.
J.R. Allen