When is it appropriate to create an entity instead of a new content type? What is the benefit to creating new entity types over just building a new content type?  

It seems a bit overkill to do all of the custom coding that is required to create a new entity when you have all of the CRUD and Views functionality already built into content types.
It's not so much about what the benefits are but more about what's appropriate for a particular situation like you've said. You can represent pretty much anything with a node and for 99% of situations (as I've found at least) you won't need to implement custom entity types.

I always think of the taxonomy_term entity type as a good example of why not everything should be a node/content type: 

A taxonomy term is essentially for grouping together different entities and as such doesn't require the same functionality as a node. While you could theoretically use a content type to perform this functionality (with perhaps a node reference field), a taxonomy term doesn't need to do the same thing as a node so it doesn't really make sense to do so. The same can be said for the user and taxonomy_vocabulary entity types.

So a taxonomy term is created as a separate entity and is programmed to do only what it needs to, while still getting the benefits of being able to have fields attached, etc.

I think the simple answer is that when a node/content type doesn't do what you need it to, or it's just a massive amount of overkill/overhead for very little benefit, then you should choose to write a custom entity.

This is only based on my personal experience; I'd be interested to hear what someone directly involved with Drupal core development had to say about this.