For a mostly non-human party:
The party is approached by an elf. He explains the following situation:
His nephew (niece, whatever) was visiting some relatives a ways away, and during the travel home was "invited" to stay with a human lord. The lord sent a message that he wanted to arrange a "lease" of some territory for his brother to hold for (say) 30 years or so. The elves are very aware that such "leases" nearly always end up being permanent. They wish to secure the return of their relative, without allowing the lease. By their standards the health of their relative is more important than the relatively small lease, but they cannot act directly as the lord is on the other side of a neighboring humano-centric country. An elven force large enough to take the relative back would have to fight its way there and break long-standing peace treaties and probably start a war. So they want someone to act in stealth for them, they cannot provide any security outside their own country. The party's job, should they accept it, is to find the relative, break it free and return to the elven territory... without causing an inter-racial incident in the process.
The lord's holding should be strong enough that a direct attack by the PC's is suicide. Be prepared to have the party try several different methods.
Some twists possible: The elf is a mage, but has lost/used up all his spells and the lord has his spell-book hidden. The elf is drugged and won't cooperate. The elf is forced by a magical curse to stay near the lord's castle. A member of the elf's retinue is a traitor and tries to interfere with the party in non-obvious ways..... (traitor is a polymorphed human?)