Folder redirections policies behave like this if not correctly removed, they have caused me headcahes in the past for the very same reasons.
I would maybe investigate client registry settings, search for the path where folders are being redirected and see if you can manually change them. Also see if you can reinstate the policy and remove it correctly also the policy my still exist in the sysvol folder of your dc's.