Translation:My colleague Matěj spoke with that artist yesterday.
The standard positions for adverbs of time are the end and the beginning of the sentence. Placing "yesterday" in the middle of the sentence is unusual and is currently not accepted. We would not normally, for example, say, "I bought yesterday milk" or "She came on Wednesday to work."
I agree with your specific examples but I disagree that it is not normal to have the adverb of time in the middle. It depends on the emphasis. If the emphasis is on when rather than on what, then having time in the middle is very common. If I am reviewing my recent schedule with my boss: "I spoke yesterday to the Chamber of Commerce. I will follow up with them today. I will meet Friday with labor union officials." I recommend permitting this translation.