The horse is created magically on-the-spot when the paladin calls for it.
This is your own house-rule. It is not what the DMG or PHB assert. For instance, if the horse is guarded by an evil fighter of the paladin's level, the implication is that the fighter may have had the horse in his/her entourage
for some time - not that the gods spontaneously gifted the fighter with an extra horse just to test the paladin!
The "magical appearance" of the horse, mentioned in the PHB and elaborated in the DMG, is talking about the horse
appearing to - ie being witnessed by - the paladin - the DMG clarifies that this will be by way of dream or vision rather than in the flesh. It is not saying that the horse magically appears - ie is spontaneously created - in the world.
Does the DMG assert that the random encounter table shouldn't be used in such a fashion?
No. My point is that it leaves it open.
If you're rolling on the encounter table, and not actively deciding that a result of "lich" will be re-rolled, then the lich already exists. It wouldn't be on the list if there wasn't a chance of encountering it. The encounter table exists, in the form upon which you roll it, because it's an accurate reflection of your chance of encountering those things.
I don't understand why you are not addressing the point.
The point is that
the GM will not have worked out, in advance, the details of every possible outcome on that encounter table. In the typical game, the GM will roll a lich result
and then decide where and how the lich fits into the campaign world. That is an act of authorship, triggered by an out-of-game event (the roll on the table). The result is that the shared fiction is developed in a way that it previously wasn't,
including the introduction of past events - such as the origins and previous history of the lich.
This sort of thing is happening all the time. It is part and parcel of being a good GM that one can do this sort of thing smoothly, without disturbing established elements of the gameworld.
EDIT: Here is a further elaboration of the point. Suppose that the GM rolls up a lich result, works the lich into the already-established fiction, the PCs encounter the lich, and they don't get killed by it (let's say they strike a deal with it).
Now, the next (ingame) night the PCs are out on the streets again, and the GM rolls a random encounter, and lo and behold, the result is once again a lich! Is it the same lich - perhaps come to check if the PCs are keeping to their bargain - or is it a different lich - perhaps a rival, tracking down the PCs to try to get them to break their promise to the first one and work for it instead?
The encounter table doesn't dictate an answer to this question. Nor do considerations of ingame causality - either is possible.
The GM will have to make something up.
Nothing in any GMing manual I've ever read has suggested that, in making something up, the GM shouldn't have regard to what would be interesting to the table as best s/he can judge what that might be.