"stroj" is one of the model words which children learn at school. https://en.wikipedia.org/wiki/Czech_declension#Masculine_inanimate
You have to get a different perception of softening in Slavic languages so as to grasp it better.
Every consonant can either be soft or not soft, there is no specific list.
Plus the consonant is not actually modified that much (it sometimes kind of is, but let us discuss that later as it is not that important right now), what actually makes it "soft" is a modest English "y" sound (as in "yes") coming after the consonant.
In the case of i and e, the "y" sound is included in the following vowel: treat (ě) as "ye" and (i/í) as "yi". (Y/ý) is a simple "i" sound that does not have the precedent English "y" sound, or, in other words, it does not soften the previous consonant.
So in the case of (Ne) and (Ny) N is not softened, in the case of (Ně) and (Ni) N is softened.
The aforementioned "different perception" means you must treat vowels as either "softening" or "not softening" depending on whether they soften the preceding consonant. That must make it easier for you to grasp the essence of palatalization.
In fact, this is why Cyrillic suits better for Slavic languages since it has different vowel graphemes for the "softening" and "not softening" vowels, but switching to it is unfortunately not even considered hence the political aspect of language.