Didn't see your version listed but I read fast and may have skipped it. If you're at 2.2 or greater the setting, "Recover grades default ($CFG->recovergradesdefault)" should take care of this for you.
I deleted some students using the enrollment method Upload Users. Now, I can't restore their grades, whether I re-enroll them via Upload Users (putting a 0 in the delete column) or manually, using the "recover grades if possible" checkbox. Where is this setting you're referring to? Is there something else I should do to restore the grades?
My answer had to do with a setting in Site administration->Grades->General settings that enables grades to be restored by default if a unenrolled student is re-enrolled. If you don't have that setting ticked (its off by default, like THAT makes a lotta sense), then you have to fashion a query statement that will update mdl_grade_grades from mdl_grade_grades_history, making sure you bring the latest iteration of a student/grade item pair over.