Well, I haven't seen any random skirmishes on my Lunatic file, but I have enough gold to afford a Scented Box. Obviously not planning on saving with the purchase, but it provided some perspective. I summoned a group of Dark Mages onto the Ch1 map, which did't seem too bad; the Dark Mages don't have any stats higher than 12. The Knight and Barbarian weren't quite so kind, but nothing on that scale. Looking at the weapons was another story: one Dark Mage was kind enough to carry Arcthunder, but the other enemies had either B rank weapons or forges. The boss used a hacked Nosferatu spell - with 15 Mt and 85 Hit, it's better than Inverse's Darkness. Shame he was only kind enough to drop a regular one.
Resetting and trying again on the Ch4 map, I got another group of Dark Mages constituting almost the exact same skirmish. In particular, the boss appears to be the same. So it looks like you're right about game progress determining it.
As for the ones you're talking about, they appeared randomly, right? So it is possible for them to show up without Scented Boxes, even on Lunatic?
Edit: Tried it again on the other available maps. Seems you can't summon monsters on locations with the merchants, so I had to sell them something so they'd leave. Each time, I got the same team - five times in a row. The enemy team was a bit smaller on the earlier maps, but the boss had the same weapons and identical stats every time. Wonder if the team was predetermined or just set up in some queue as the next one up.
Edited by Othin, 07 May 2012 - 03:49 PM.