I tested ‘Search-regex’ plugin for non-admin user with ‘search_regex_read’ capability in a role without problem.
‘Broken Links Checker’ plugin uses ‘edit_others_posts’ capability for its menu item under the ‘Tools’ menu. Does your role include ‘edit_others_posts’ capability?
