Is the only way to complete this quest is to side with Locke? I don't want to be that evil

You can side with the soldier; when you say you believe him that completes the quest. If you return to Locke after that you can accuse him of using you to extort money, but (at least in D2:ED) that only results in him raising his prices. You can simply avoid that conversation option, though, if you wish to keep the option of being able to trade with him.

Thanks, I always sided with the soldier. I just found it a bit strange that the only way to tick this quest off was to be a arse. that said, I did my first Bandit camp quest last night, helping two ex-murderers

I always sided with Locke for having better prices!

Urgh, Can't stand the man. shame there wasn't a option to dismember him and stuff him in his cart (password has now changed to: Guts, more guts)

Yes.
Explanation:
http://www.larian.com/forums/ubbthreads.php?ubb=showflat&Number=384814 (last post)

I completed the quest and got the experience / reward when I told the soldier I believed him. I don't really care if the quest is classified as failed or not, as the only thing that effects is the colour of the text in the quest log (I did the quest both ways in D2:ED, and if there was a difference in the reward it wasn't enough to tempt me to help Locke).

Funny though how everyone assumes Locke is lying just because he is a sneaky fellow. There really is no proof that the guard is honest. Maybe he did rip Locke off, you can't be a 100% sure.

Locke is a honest man, but his acts are driven by .... trading and especially his goldcoints, Gold, more Gold !!

Mindreading him and do the little quest for him and he lowers twice his prices ! And he has often very nice items !!
Me, I just do it for having the best prices I can and don't worry about the quest solution is evil or good .. I just look for my own pocket filled with Gold, ... moooore Gold ...

Are you saying that mindreading isn't 100% foolproof and can't be tricked? Now that's interesting. It is hard for me to imagine that some soldier who, probably, never heard of mindread and has no special powers/abilities, can resist mindread. But oh well...

Your point being? He can't resist mindread and there's nothing in his mindread that reveals more about his relation with Locke, only Richard.

It's obviously implied that Locke is playing tricks, but you can't be really sure.

This one actually made me lol.

Its obviously implied that its obviously intended to be non-obvious in its ambiguity

Exactly!

Exactly. That's why quest feel incomplete and way to artificial (made up) - mindread says nothing (but in many other quest it DOES say much, directly).That's.. weak way to make a non-obvious quest, but oh well... it's disappointing that we don't have much choices how to complete quests in D2. Really, we have all tools to find the truth (or acceptable solution): mindread, status, ability to speak after all.. but no, devs put artificial barriers and create only one way to finish it. During both of my walktroughs (there was 3, actually, but I never finished the 3rd one), i always left that quest incomplete coz I didn't like the way how can I complete it. To make a player to do NOT want to finis the quest - that's quite a talent I say :P

Here's something to consider with Locke's quest (and this may answer questions about other quests as well).

Locke is the quest giver. What this means is he sets the parameters for what constitutes succeeding. Macbeth's argument aside, the quest is not "resolve this situation," much less "resolve this situation in a good, not evil, way." It is "get my money back from the guard."

While helping the guard may very well be the "good" thing to do, with getting the money being "evil," the quest is quite specific in that you must get the money from the guard and return it to Locke.

No one ever said every quest must be just, nor are quests any more than an errand at the behest of the giver.