task approver needs to have

- read permissions on list where the workflow runs on (if you allow approver to change list data in task form he/she need edit permissions as well)

- contribute permissions on workflow task list and given task/list item

once you delegate task, required permissions are given to delegatee on given task list item.

however you have to ensure delegatee already have sufficient permissions on workflow task list itself.

from your description I can not identify exactly how do you have set permissions on all of these

- list the workflow runs on

- list tem

- workflow task list

- task list item

so check whether all of these you have set correctly.

The delegatee has contribute access to the item, the list the item runs on, the task list item as well as, the "Workflow Tasks" list. Still, when they go to complete the task they receive a message stating they do not have access. However, when I turn the list setting from "Create items and edit items that were created by the user" to "Create and edit all items", they can do the task. However due to function of this list, this cannot be done because this then gives users the ability to edit all items.   

If you have item level permissions for the list set to "Create items and edit items that were created by the user", then that overrides whatever access the delegate has to the list.  So essentially they don't have contribute access to the list item.  If your requirement is that a user can't have access to edit all item, yet you need to be able to delegate a task to someone and have them make updates, then you may need to control the permissions on the items on that list via workflow.  Instead of setting item level permissions, set the permissions to items with a workflow when items are created.  Then when you delegate a task, you can add the delegate to the permissions for the item so that they can make updates.  

Exactly!

I have tried that. However, users then have permission to edit current items running on the old workflow and these items cannot have their workflow's cancelled and restarted on the updated one (Without a very good reason). My understanding is that the delegation is not an option for the list unless they allow to restart the workflow on all existing items. Correct?

Cody, I'm not following.  What do you mean by current items running on the old workflow?  And why do you need to cancel and restart a workflow?  If you're using the delegation function of the flexi-task, the workflow doesn't restart.  When the task is delegated, the assigned to person on the task is changed to the delegated user and they get a notification.  They complete the task, and then the workflow proceeds.  You can use the permissions part of the Flex-task to give permissions temporarily, but it will only work if item-level permissions are turned off.  

Yes, but once you alter, save, and publish the updated workflow (that will set the item's permissions) and change the list setting to "Create and edit all items", users cannot edit new items running on the update workflow (which is correct). However, they can edit already existing items running on the previous workflow (the version withOUT setting the items permissions). The already existing items would then need to have the old workflow cancelled and then restarted, to allow the permissions to be handled via the updated workflow. Follow?   

Yes, I follow now.  You are right, you'd need to go back and set the permissions on the existing items on the list.  You could build a workflow that would go through each item and set the edit permissions of that item to just the user who created it.  It would be a one time change.  I don't think you'd need to restart all the in-flight workflows.  The only scenario you'd have an issue is the one in which the task is delegated.  But you could also account for that as well.  You could have another workflow that runs on the task list and is triggered if the assigned to field is updated.  That workflow could go and update the permissions of the item to give the delegated user access.  Then it could wait until the task is completed and go and remove the permissions.  But that may be overkill depending on how often you think that would happen.  If it's only a few task, it may be better to just handle it manually.