If they have an adjusted timesheet (which I think you are saying they do have), where the old/adjusted timesheet contained a task on that project (even if the new/adjustment timesheet removed that task), then the system will not let you remove that resource from the project (just like if they had a 'real' timesheet against the project). Its a "commited actuals", even though you have cancelled out those actuals subsequently.
I think all you can do is make their allocation zero and remove them for time-entry on that project.