I see and can repeat a problem at my test environment. Thanks for your help in discovering it. I will publish the update in a week.

When you use ‘Block not selected’ model at ‘Admin menu’, URE allows just exact URLs linked to the selected menu items: users.php for ‘All Users’ menu in your case. Pay attention – without any parameters. But when we search a user, an URL will be:
Pay attention on a list of additional parameters added to it.
URE counts such URL as prohibited, that’s why contributor user is redirected to the 1st available menu item every time he try use a search feature at the ‘Users’ page.

I should add those parameters to the list of allowed parameters for the user.php URL, but I missed this.

Temporal workaround – switch to the ‘Block Selected’ model at ‘Admin menu’:
– select ‘Block selected’ at the top, then click on the top left checkbox with a ‘Shift’ key together – this will invert menu items selection. Save your updates.

Recommendations: try to exclude unneeded menu items by revoking the related user capabilities 1st. Use ‘Admin menu’ to block menu items just for menus which you can not exclude via user capabilities, like in case with ‘edit_posts’. ‘Admin menu’ is the extension to the core permission system. But ‘user capabilities’ is primary defence level.

You can easily exclude some menus without ‘Admin menu’, just by revoking ‘manage_links’, ‘manage_eventon’ capabilities from ‘contributor’ role.