I've used the analyze permissions utility to make sure the permission for that user has a positive value. Yes, it does.
As a final step, I've used the test permissions utility. Unfortunately, it does not show the edit link in the footer of the messages by that user, yet if I log in as that user, the edit link is there.
Is this by intention or omission?