For years I’ve used custom fields (post meta) in WordPress as a primary storage area for misc. data about specific posts (including pages, custom post types, etc.). Recently, I’ve realized that I should be using custom taxonomies instead of custom fields in a variety of situations.
Custom fields are still the right choice for misc. data that is used for display purposes only, or descriptive data about a post that is used by a behind-the-scenes process. You can serialize data here to store the equivalent of cached relational data. You can set flags for various behavior triggers, etc. You can also create a custom user interface for adding and editing the data you need to store.
Where you should use a custom taxonomy instead is for any data that you need to query on. For example, getting all posts that were broadcast to Twitter; all posts that were created by an outside process; all posts that have a certain workflow status.
The reason to favor a custom taxonomy in these situations has to do with the WordPress database structure. Queries by taxonomy are well optimized as this is a primary front-end presentation feature in WordPress core. Conversely, querying by custom field key and value is slow. The value column in the custom field table is not indexed – you are basically doing a search through data that is not intended for that purpose.
(Yes, as a workaround you can create a NoSQL-style composite key that contains both the key and value in the key column (key = ‘featured-yes’ instead of key = ‘featured’ and value = ‘yes’), but there are only a handful of solutions where I’ve thought this is a more elegant solution than using a custom taxonomy.)
Remember, you can still create a custom admin UI for your custom taxonomy (perhaps to enforce single selection, hide certain options in certain situations, etc.). Or you could choose not to expose the data on the front or back end at all and just manage it in code behind the scenes. However, if you do want to expose it, WordPress already has a bunch of tools to let you do this (clean URLs, pagination, feeds, etc.).
I think my previous mindset of being focused primarily on using custom fields is partly because they existed before custom taxonomy support was part of WordPress core. One of the hardest things to do as a developer is realize when things have changed and part of your library of knowledge is no longer accurate/relevant. I know I harbor grudges against various apps, platforms, etc. that are certainly based on outdated information (I just don’t know which ones).