Well first of, there is probably a way to delete the traces in the registry like you mentionned, as long as the software is not using anything too sofisticated to track previous installations (like hidden files or hidden keys in the registry that you can't easily find...). You should start by deleting the program folder after uninstalling it, then look for anything in both HKEY_LOCAl_MACHINE/Software and HKEY_CURRENT_USER/Software for anything that has either the name of the software (plain and simple) or the name of the company that made the software.
Delete those keys once you're sure it's related to that software, and try to reinstall.
If you still can't do it, I suggest that you contact the technical support of that company. You paid for a piece of software and they can't prevent you from reinstalling it on the same computer! That is illegal! Unless the license agreement specifically says so (which I highly doubt) you can probably not install multiple copies legally on other computers, but you should be able to reinstall it on the same PC...
They HAVE to let you reinstall. What if your PC just crashes and you have to reformat? You'd have lost 75$?? No way. Try the above and let me know what you find.
PS. What is that software anyway? (Do you have the website link?)