"He researched it" is no better than saying it was divine intervention.
Its not a get out of jail free card, theres absolutely no fucking way he would know about this random nobody dying somewhere, as if that world had fucking security cameras he could view or something.
Today you can just walk into a library and look at the newspapers of the last century, in a world like that shit that happened last week is already a mystery, him knowing obscure shit that happened decades ago is completely unbelievable.
Do you really need me to say that “fucking security cameras” is not the only source of evidence for the (not so distant) future?
This world has some military police and thus, most definitely, also has some regular police. It does not have cameras or computers, but it has paper, and on paper any such police has to have some fat logs for any crime scenes such as “Imperial year 908, April 11th, found a corpse of a young woman of the corner of Bell Street and Haven Avenue, several wounds, signs of heavy internal bleeding.
UPD identified as Lucia Dynes, see logs of the next day”.
Whoever “they” are (in the phrase “you should get away from here before they come back here”) are probably also an organisation that keeps some logs. Or maybe Kaltz talked to an eyewitness that he found in those 10 years he spent preparing.
For the record, when Kaltz thinks “I've spent 10 years preparing”, what can we see on the background?
That's interesting, isn't it?
On the left part of that panel we see a telephone. That's definitely not a smartphone and not even a mobile phone (it has a cord), but that's already something. Our guy Kaltz does not have to spend all these years in travels, he is able to call someone by his phone (and perhaps apply a bit of “social engeneering”) whenever he needs to dicuss an event of the fateful year in the past.
On the top part of that panel we see at least five electric switches. The Divine Tree Empire Alvisage seems to have some electricity (or, at the very least, an equivalent distribution of magic energy by metal power lines).
On the right part of that panel we see something that looks very much like an equaliser below an audio speaker. So, in addition to paper trails, sound recordings of eyewitnesses might be available.
There are also some signs that imply that you are wrong when you assume that Lucia Dynes is a “random nobody”. She is at least significant enough for Kaltz to identify her (in the future) as the first in the list of persons that would make good allies if saved or otherwise helped by him:
That means that she is at least significant enough to leave a paper trail behind that eventually reaches Kaltz in the future.
Or, even if she isn't, an alternative explanation is that Kaltz of the original timeline has already seen Lucia Dynes dead in the slums where he lived. And thus he does not need other eyewitnesses or paper trails, he already remembered the exact coordinates where he needed to be in the past to save Lucia. All that Kaltz needed in the future was to confirm who Lucia Dynes was (i.e. why she would be a good supporter for his plans).
There is a good chance that you are wrong when you imply that “today you can just walk into a library and look at the newspapers of the last century” is an event that could not happen in the Divine Tree Empire Alvisage. After all, here on Earth we had newspapers for a few centuries before telephones, and there in Alvisage they already have telephones (if I am not wrong about the panel I quoted above). So, unless magic greatly affected their routes of technological advancement, they might have newspapers already.
(We should not underestimate the inventions that are made possible much earlier when imperial magic is applied to devices of the dawn of our own technological era. For example, they defininitely have magic golems, and thus their magic nobles might even have specialized golems working as answering machines for their phones already.)