Symptoms
The issue is that on a newly created Related list, the "Edit" button is not visible, even after un-checking the "Omit edit button" checkbox.
In this case, even the "Enable Edit" button does enable the Edit button on the related list.
Release
All releases
Cause
One of the causes this will not work is because it is not a Related List but a "Relationship".
The record will have a name such as "REL:xxxxxx" where "xxxxx" is a sys_id of the related list.
This determines that this is actually a Relationship, and relationships will not get the edit button when you click the Enable Edit button from List control. Related lists that are based on a relationship record do not have the Edit button available because it is the relationship itself that defines the records that appear in that related list. The edit button does not make sense in that context. To move records into and out of that related list you would update the target records so that the either matched the relationship criteria or make it so they no longer match.
Resolution
You can get the Edit button not from the List Control, but directly editing the Edit Global UI Action.
"Edit" UI Action: nav_to.do?uri=sys_ui_action.do?sys_id=7fff4c3d0a0a0b3400ad3f1a1d613f74
You can either modify the condition field in the UI Action to fit your requirement, or create a new global Edit UI Action. Keep in mind that any changes to this Edit UI Action will reflect throughout the instance, since it is global.