In that case, the CD key was probably stored in the registry, and not removed when the rental was un-installed. The saved game formats are more than likely not tied to the specific CD key, so there should not be any problems using a different key (unlike with online games). If you ever need to reinstall the game, or move to a different computer, you can use the CD key you have.
If you are comfortable editing the registry, you could change the CD key (HKEY_LOCAL_MACHINE\Software\LarianStudios\BeyondDivinity), or uninstall the game, run a registry cleaner and re-install.