But they appeared in the same location both times, with the same (non-full) HP, just after I killed them.

PS: Also, after I left them behind, I got a message that my sovereign was attacked, but no combat window or battle (and I have no limit for tactical combat). And THEN the group was decimated (only their leader survived the non-encounter).

What I perceived was:

Round T (LastAutoSave): A band of bandits is standing left of my sovereign. I attack and kill them.

Round T+1 (AutoSave): The same band is still there, same names and health. I leave.

Round (T+1 => T+2): I get a message about someone attacking my sovereign. I get no battle report, and no tactical combat.

Round T+2: The band of bandits is now north of my sovereign, but only their leader is still alive.