Hi fabien,
It does sound like you may need a registry hack. If you fully uninstalled both versions, rebooted and tried to reinstall and you get this error then you probably have something hanging back in the registry. I believe I had to do this a couple of years ago. I suggest you to do a manual uninstallation. http://seer.entsupport.symantec.com/docs/250510.htm. IT tells you the exact registry keys to delete. Failing that do a search in the registry, after backing it up of course, for veritas and BE and get rid of the entries. After that it should allow you to reinstall without problem.
Kevin