When I asked my teacher for the gender of Mensa, she replied that it is feminine, because the Latin word mensa is feminine. When it comes to words that share the same spelling in both German and Latin, is this generally true?
It is largely true, but there are exceptions with false etymologies or old words that have been modified a lot or words that look like the opposite Latin gender to a non-expert.
fenestra (Latin, female) -> Fenster (German, neutral), both mean window.
arcubalista (Latin=archer, male) -> Armbrust (German=crossbow, female, false etymology arm+breast).
Latin and Greek were both very alive in Germany in the 19th century. This might be one reason why this kind of argumentation and also the knowledge of which latin ending belongs to which gender is still very common. (And a word like "Mensa" might even be introduced during just that very time, but that's just a guess.)
A nice example of how this works in German is the plural of the word "Status". "status" derives from Latin and belongs to the rather uncommon u-declination, so its plural is "status" [ˈstaːtuːs]. This is still the "official" plural in German, too. (according to Duden, for example).
However, you'll hardly ever hear [ˈstaːtuːs]. Instead, people will use "Statusse", or - and now comes my point - if they try to be clever "Stati", assuming this would be a Latin o-declination.
So, the connection between -a -> female and -us -> male, plural -i is obviously very well known. Probably because its one of the first things you'll learn in Latin lessons, so it stuck with people. :) Another one is -or, which is always anticipated to be male.
Word like "Fenster" and "Mauer" came to German ages ago, so the connection got lost completely. Also, there's no -a or -us in there so you can't really see where it is coming from.
I think that it's important to distinguish between two types:
Words that were adopted into the german language in old times, maybe even during the roman empire. As the other contributors have pointed out, these words have changed and degenerated over the centuries and now have often different articles than their origins.
Words that found their way into German through Latin as the language of science in Germany until the early twentieth century. (I still have an old Greek dictionary from school with a preface in Latin. And I'm only 23.) Those words were - and still are - majorly used by the educated classes and have preserved their gender and orthography.
So - to answer your actual question - if you find a word that has exactly the same spelling in German and Latin, you can be pretty sure that it belongs to that second type and has preserved its gender.
As always: Be aware of traps!