Companies that actually sell things will just buy tags (it's buying _advertising_ after all, and that's what we do) that they think even slightly matter. Also, "free" apps are hard to classify in today's environment. Just because I don't charge for the app itself doesn't mean that I'm not making money off it, between in-app payments, in-app advertisements, and product synergy.
In the end, users don't search for apps with tags (aside from the very broadest categories) that much anyway. The app store is going to have a group of people whose job is to select "featured" apps and place them on the front page before users even select tags. That's where users find apps. And that's what app developers strive to get into.
The rest of the users are going to find apps via Internet links, so it's very important to make sure there's a URL scheme for loading up a particular app in the app store from the device's browser. That way a review of the game on GameSpot or PocketGamer or whatever can link directly to the app info/purchase screen in the user's phone.
(Bonus points for making this an HTTP URL and not an actual HTTP scheme, in which the device browser detects the URL and loads the app page internally but other browsers load up a regular page, allowing the user to view and purchase apps on their PCs by logging into their app store account, and then have it automatically downloaded to their device.)
The silly model that the Linux package repos keep pushing of the 50 categories and sub-categories and split-up packages aren't how users work.