Forticlient 5.6.5 and 5.6.6 can´t install - uninstall old version first

Are you using EMS server as well?

Are you running the proper FCRemove.exe - the one for the specific version of FortiClient that is installed?

Are you running FCRemove as Administrator? (not sure if Safe Mode bypasses UAC or not).

If you are not using EMS, it sounds like the root issue is with your GPO. Like it's trying to keep users are a certain version, or looking at certain libraries or something on a users machine as an indication of GPO adherence. Then, it tries to change version but is not uninstalling it properly, leaving some "cruft" behind. Then you cannot remove those legacy software components, because they are being enforced by GPO.

Maybe try creating a new GPO that runs FCRemove.exe and applying it to a few test workstations.

Lastly, you may (or not) have luck using a 3rd party uninstaller like Revo Uninstaller. Been awhile since I used it, but I think you would need to use a test laptop that doesn't have FortiClient installed at all. Install it via Revo so it can build a profile of all DLLs and such it installs, and registry entries it creates/modifies. Then run through the uninstall process using Revo and use that output as a template to nuke all traces of the software from other machines.

Hope some of that helps.