I've figured out a solution in case anyone else comes across this problem.
The createOverrideVariable() is not persisted which is the reason why setting it does not cause org.eclipse.cdt.utils.envvar.PrefsStorableEnvironment.notifyLanguageSettingsChangeListeners(IEnvironmentChangeEvent) to fire (I'm not sure whether this is by design or an omission?). I need this to be fired to rerun the scanner discovery after my toolchain is added to the PATH environment variable.
A workaround is to set a dummy workspace environment variable which causes notifyLanguageSettingsChangeListeners() to fire and then the scanner discovery reruns, this time without any problems finding my now PATHed toolchain. I delete the env var immediately so it can be created again on the next launch.
UserDefinedEnvironmentSupplier udes = EnvironmentVariableManager.fUserSupplier;
StorableEnvironment se = udes.getWorkspaceEnvironmentCopy();
se.createVariable("dummy", "");
udes.setWorkspaceEnvironment(se);
se.deleteVariable("dummy");
udes.setWorkspaceEnvironment(se);