The Run Unrestricted setting on saved searches does not supersede the record permissions set to the user's role. Unless the user has permission to the record type used for the search, running the saved search unrestricted will still not allow the user to view the search results.
Rather, Run Unrestricted only applies to search results that the user will normally not see due to class, department, location, subsidiary, or employee restrictions.
To allow a user (with Department restriction set to his role) view all items regardless of their assigned department:
1. Navigate to Lists > Search > Saved Searches > New.
2. Click Item.
3. Mark the Public checkbox.
4. Set other criteria as needed.
5. Under Results tab, set Run Unrestricted=T.
6. Click Save.
Run Unrestricted will only allow restricted users to view the records from the search results. The Edit and View links will still not be visible for them for records that they are restricted to.