Interesting point on the GC aspect of the action, I hadn't really considered that angle.
The God in question is a homebrew God, somewhere between Tyr (FR version) and Cuthbert (Greyhawk version). There is a separate "shiny knight" (roughly a cross between Torm and Pelor I'd guess) God with Nobility as one of her domains, so there is a pretty clear distinction in the pantheon, although both churches support Paladins. The pantheon was developed by the DM with players' input, in this case there was interest in both the "knight in shining armor" paladin and the "gritty, relentless paladin" archetypes.
Raising an army is an attractive option on the one hand, but for out-of-character reasons I think the Paladin would risk highjacking the campaign, since that would take a lot of time and money. No one minds if a single session focuses on 1 player, but if that continues for a few weeks, then I'd guess players would start to grumble.
A few minor points:
The Paladin never lied. He told the bandits who he was looking for and he told people who had not participated he wasn't interested in them. It's roughly the same theory he uses when he dons his Robe of Disguise. He can dress up as "a noble from the South" but he would never, ever dress up as "Sir Garl, Grand Count of the Isle Kingdoms." Walking around in full platemail is cool and impressive, but it really makes talking to the local population tough sometimes.
He also never presented himself has a member of the Church, although he obviously didn't pretend to be a member of a different Church either. In his mind (other clergy might disagree) he was actually doing a great job of representing the Church, after a fashion. "You mess with us, this is what you get"
In some cases, the above 2 examples could be seen as splitting hairs, or seen as theological differences between the 2 LG churches. Obviously, the session is over and a call was made by the DM, but we all thought it would be interesting to throw the scenario out to the enworld population, since there are many different and legitimate takes on Paladins here.
Final note: The Paladin in question has spent a ton of ranks on Profession (Judge) so, mostly because of that, Church law has been fleshed out fairly well. Currently, his church is at war with the CE church who hired these mercs in the first place, which means martial law applies, so this is not the kind of behaviour one would expect if he fought a pack of bugbears.