Taxonomy vs Post Status

Probably post_status but this answer is probably irrelevant in your case. You have your own application with its own usage pattern of the DB therefor the assumptions used when designing wordpress DB for use by core might not fit you. Maybe you will need to add another index to the posts table, maybe create optimized table of your own.

Caching is also an important factor. If the data set does not change frequently then good caching scheme will make the speed difference irrelevant.

This question sounds like an attempt in early optimization. My suggestion is that you use the built-in tools (post meta data in this case might be better then taxonomy) to get your application running and then you can profile it and solve the real bottle necks and not the imaginary ones.

tech