The source of the issue is that admin menu item ‘All Posts’ (edit.php) is prohibited (selected) for the role, but allowed are ‘All Pages’ (edit.php?post_type=page).
When user try to search some page, URL becomes edit.php?post_type=page&s=something…
which is not apparently allowed and edit.php is in the list of prohibited URLs. Thus URE fulfills the redirection. The same is similar for other custom post types, URL for which starts from edit.php too.
Quick workaround is allow for a role ‘All Posts’ menu and submenu items. I tested this for IU administrator role and left as it is for your review.
Let me know if this workaround is suitable for you. If it is not, I may offer you a piece of code which will hide ‘All Posts’ menu items from admin menu directly after adding to the active theme functions.php file.