Why "měl + verb" is sometimes translated as "should + verb", and sometimes as "should have + verb"?
It depends on the tense/mood of the Czech sentence. (Look carefully at the verb in the Czech sentence.)
present tense -> should + infinitive
past tense -> should have + participle
present tense -> should eat
past tense -> should have eaten
Note that in English there is no past tense of the verb "should" itself, so English works around that by changing the tense of the following verb (from the infinitive to the perfect infinitive).
The last paragraph is not quite true. There is no verb "should". "should" is past tense as well as conditional of "shall".