Well, I haven't posted anything in a while so here's somehting for all my fellow techs:
If you've done everything you can think of to a GPO that's applying folder redirection but just can't get it to work for some users, check this:
Click Start button, right-click on "Documents", choose "Properties":
If it's been customized, the GP won't override it. Revert to defaults and ta-da, it works!
(obviously, the above documents folder is not directed to a server - I didn't want to show the customer's info publicly so I screen captured mine for the example).
In my situation I was moving a customer's profiles from one server to another and this user's folder (135 GB) moved automatically (mostly - 8.5 GB was left behind) but his computer was still referencing the old server location. From the user's perspective, his files were missing (only the 8.5 GB was visible to him). Once I hit the "Restore Defaults" button, and I manually moved the remaining files, everything worked perfectly.
Could I have manually configured this to solve my problem? Yes, but then it would have bit me next time too. This should solve it for good.
I couldn't easily find a solution to this on Google so I've posted it here.