Tagnautica is a very cool tag based PHP browser application that helps you explore Flickr photos. I recently read about the application created by Mario Klingemann from Munich, in this post by Phillip Lenssen.
In giving the Tagnautica a try I searched on tags of my name "FrankGruber" and it returned nothing so I then I searched on "SomewhatFrank" and was skunked again. So it appears to me the application is not searching all of the tags in Flickr because I know that I have tagged certain photos with these tags. Finally, I used a more obvious search keyword term "LosAngeles" since I am currently out in LA and I was took the screen-shot which is above. I would recommend giving Tagnautica a try since it offers a creative results set display and is worth a look. However, since I could not find results to all searches I performed it may not be the answer for searching on all tags. For more information on Tagnautica check out this post on Information Aesthetics.