Interesting ... first ... which version of Moodle?
Are you allowing guest access to anything?
What happens if one doesn't login and goes directly to http://site/tag/search.php ... does it show auto logged on as guest user? (upper right hand corner of screen)
What does 'view the entire folder structure' look like? You are not saying it list files are you? Or does it show icons for users who may have used the same tag? That does disclose their full name with mouse over.
As far as permissions on tag:
A search of capability overview for 'tag' shows that
Create new tagsmoodle/tag:create is allowed for Manager and Authenticated User.
Guest is an authenticated user. However, attempting to go directly via URL without logging on to any of the scripts located in /tag (other than search.php) results in user being prompted to login.
Check the following settings: http://yoursite//admin/search.php?query=profiles
'spirit of sharing', Ken