I have a Torah in my shul that does not have any large or small letters where required (e.g. - the 1st letter in the Torah, "Breishit", is written larger than the rest.) Is this Torah still considered "kosher"?
Obviously if they can be fixed, one should do so to conform with the tradition.
DoubleAA is correct that a Torah that is missing scribal traditions is still valid.
However, if another Torah is available, the Torah inconsistent with tradition should not be used. (see Shevet HaLevi 4, Yoreh Deah 141)
In addition, if the Torah was from a tradition that normally conforms with the small and large letters and, nevertheless, is consistently missing them, this casts doubt on whether the sofer was careful in the other aspects of writing a Torah (e.g. writing the name of Hashem with the proper intent, erasing parts of letters causing a psul of chok tochos and so on) and the Torah should not be used. (See Shevet HaLevi 4, Orach Chaim 1)
As a matter of fact, in pre-War Europe it was well know that the scribes of Slonim were not meticulous when writing the Torah and the Torahs from that location were presumed invalid (b'chezkas pasul). (Heard personally from preWar Roshei Yeshiva and is generally well known among scribes, Os Chayim V'sholom 39:1 footnote 13 here)