Yeah, that one's a bit tough, as it's one of the first missions you'll encounter in DS, and the soldiers have loads of hit points.
To make matters worse, it's difficult to isolate them. They're mixed in with Wandering Wizards, so very often you have to endure an entire battle just to get one of them. I never understood the point of alternating the enemies like that. This is even more frustrating when you add in the percentage FAIL to collect certain items.
On the bright side, once you get past the soldiers mission, things are pretty reasonable for a while.
