Interesting:
The first example is drawn from my homebrew:
1) The Paladin is a member of a nation which is ruled by acredited craftsman. Guild officials not only govern their trade, but the trades collectively govern the nation. Particular trades hold permenent roles in government. For instance, the Minter's Guild is equivalent to the office of the Treasury. The Mercenaries guild is the army. The Shipwright's guild controls the navy, and so forth. In this society, the Thieves guild is an official institution of the government and provides an important service - namely, in its official capacity, it is the office of foreign service and intelligence, or 'spies' and 'counter-spies'. It just so happens that on the side, the guild still continues to regulate and ply its more ordinary trades - smuggling, racketeering, theft, and so forth. This situation is tolerated by the other guilds in exchange for promises to keep its illicit activities suppressed above a certain level. In such a situation, the Paladin could work both as an agent of the government, and as a guild enforcer responcible for tracking down 'rogue agents', and be reasonably detached from the skullduggery that portions of the guild engages in.
2) The Paladin as a result of a pledge of honor is honor bound to protect the life of a high ranking thief who has saved his life and/or rendered some other service which the Paladin's code compels him to repay. Provided that the particular thief in question is only a rascal and not a particularly sadistic SOB, the Paladin could for quite some time continue this relationship of indeptedness. An example which appears to be something like this in fiction is Han Solo and Chewbacca. Han is clearly a rogue, but not a particularly nasty one.
3) The society is so corrupt, that an honorable Paladin can only continue to live in honor, by breaking the laws of the society. For example, the Paladin could be a member of a guild roughly corresponding in character to the legend of Robin Hood's Merry Men.
I think these can be made particularly strong by using two or three in combination.