While I think that the site could use a restructuring along OS specific lines (Solution 4), in the short term I think that removing restrictions on the Advanced Search screen (to allow a search without a keyword but with the other, existing filters on the screen) would do much to relieve my heartburn. (Solution 5)

I wouldn't hold out much hope for tags. If you provided a list with checkboxes where the smilies list now shows up, you might find more people using it but many people don't bother and without a list of possible tags the variation in tags makes searching on them no more useful than searching on the title or text.