As a DM, I'm less concerned abou the "legitimate authority" limitation. That can be rationalized one way or the other. And in fact, a good DM may allow some latitude in attitude, if he is to get a party together that isn't trying to kill each other or refuse to work together.
From the SRD, I glean the following behavior rules (
http://www.d20srd.org/srd/classes/paladin.htm):
must be of lawful good alignment
respect legitimate authority
act with honor (not lying, not cheating, not using poison, and so forth)
help those in need (provided they do not use the help for evil or chaotic ends)
punish those who harm or threaten innocents.
may adventure with characters of any good or neutral alignment
never knowingly associate with evil characters
discontinue an association with someone who consistently offends her moral code
may only accept henchmen, followers, or cohorts who are lawful good
So to sum up, the paladin can't hang out with evil people, or do evil things. Therefore, the members of the Guild can't be evil, and they can't do evil things. The Paladin won't be able to help with some less honorable tasks (stealing or swindling).
The paladin might be able to act as a highwayman (Stop villain! Surrender your money or face my steel in combat). But anymore than that might be pushing the limits of the code of conduct too far.
Played strictly, a Paladin will have a hard time playing with any party that isn't deliberately designed to work with the paladin. And that restricts other players fun (and I'm all for players making PCs that can work together, but when somebody says "I wanna be a paladin", everybody else has gotta fall in line and that's rather unfair).
Let's get back to the OP, however.
Here's the ideas I've seen so far in this thread:
corrupt government, paladin finds unlikely allies
honor debt to a rogue/guild
paladin is fed info to work against guild's enemies
honorary membership in guild due to past good deed
Here's some others:
paladin is forced to work for guild (threatened, magically induced)
paladin is sent as liason to guild for some cooperative project (has to tolerate them because of orders and specificity of the mission)
rival guild which is more bloodthirsty than 1st guild is setting up in town, paladin needs help, so he forms a truce with 1st guild)