How to tell if cheese is vegetarian?
Unfortunately, as you suggest, this is tricky. The short answer is: if it's labeled "vegetarian rennet," "vegetable rennet," or "microbial rennet," it is probably, but not necessarily, vegetarian. Otherwise, it is probably not vegetarian.

If you're willing to substitute different "cheeses:" Consider cheese types (or cheese-like products) made without rennet in the first place, such as acid-set cheeses or bacterially-cultured cheeses, like quark, cream cheese, queso blanco, paneer, certain types of ricotta, crème fraîche, marscarpone, etc. Clearly some of those are more traditional "cheeses" than others.

As for more mainstream cheeses: There are various guides, such as this one from The Vegetarian Society with a little more detail, including nuggets like that proper Parmesan (Parmigiano-Reggiano) cheese is never vegetarian -- i.e., DOP/PDO certification guidelines specify the use of calf rennet. Whey cheeses like mysost or traditional ricotta are also unlikely to be rennet-free, because the whey used is often a by-product of "conventionally" processed cheese.

Some places around the world have better markings; e.g., in India there is the vegetarian mark, which is required on certain packaged foods. In the US, for instance, there is no federal, legal definition of "vegetarian," though there are now some certification bodies (akin to Kosher or Organic) as noted in this Vegetarian Resource Group article. Other companies and markets have their own hieroglyphics (e.g., vegetarian, vegan, gluten-free, low-sodium, ...), but they're not always clear nor are they standardized. 

A couple other sites have guidance, such as Vegetarian Times, or lists such as Joyous Living.

For completeness: Make sure to understand the source of microbial rennet to make sure you're okay with the possible sources, but this wasn't really your question. Similar problems exist for determining the vegetarian-suitability of "natural flavours" or other additives, but that's a different question also!