Another solution to this problem would be competition. If there were a workable alternative to Gmail that had account recovery mechanisms better suited for this population than the librarian could simply recommend that for their patrons.
Can anyone suggest what a good alternative to Gmail would be for this population?