Saved Searches on the My Items object are available in the drop-down menu in the My Items workspace, even if the search is explicitly not published to the Self Service role. It appears they have access to all of the saved searches on that object, even personal-only searches.
There are three conditions that determine if Saved Searches display;
First is the publishing to available roles.
Second is if the current login user is the owner of the Saved Search.
Third is if a role has the right to edit searches in system permissions.
The third criteria is driving the behavior - the Self Service role had the right to Edit saved searches.
To remove this right;
Log into the Admin role
Select Configure Application
Select Users and Permissions -> Roles and Permissions
Select System Permissions
Uncheck Edit (for all) in the Search row