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 it's true for words with the exact same spelling, although I think the overwhelming number of loanwords have changed spelling and pronunciation in their German version. For these cases there are exceptions, for example: