What it seems like is that the ex-party member has mortgaged quite a deal of resources in order to get a huge threat on you guys. It's the details that are going to be important here, because they limit and open your options.

Do you guys have the reputation and/or social skills to rouse the town against this 'invading pirate force'?

Do you have the resources to by contingency raise deads for the party triggered on your body being delivered to the ex-party member, allowing you to throw the fight against the mercenary, and bum rush his employer?

Do you have enough information or tracking ability to be able to dodge the mercenary force and slay their employer?

Can you convince the cleric that his deity is on your side of the conflict?

I could keep thinking of options like this, but just knowing your levels and classes isn't going to tell me much on the fine details that matter when you're massively out CR'ed.

Recruit Get as many NPCs on your side of this conflict as possible. If this town is ruled by money, then there are bribes you can make, bounties you can place on the cleric's head. Greed is king here, and greed is indifferent and disloyal, so use that.

Sapping Yes opium and other means applying wisdom damage to the Cleric is a great option. As for the gun powder. That'll work once. Then the cleric will resist fire, so the second time, you put the gunpowder pile on the other side of cheap wooden wall, and spray him with shrapnel for piercing damage. If possible toss negative levels at him as well. Also, if you can steal or destroy his divine focuses (holy symbols usually) most of his spells will be untenable.

Information Figure out as much as you can about about the cleric, and use it against him. Find out what his god tells the cleric not to do, and make sure that is the fastest way to you. Figure out how much these pirates are being paid and see if you can get them to betray him.

Accounting Tricks Money talks, and it can also lie. If you can negotiate for paying 'half up front' or 'money when you give me his head' you don't actually need to have the resources you're promising to give later. It's much easier to evade dozens of low level debtors then it is to evade a single level 15 cleric.

Distract If the cleric is being guided by his 'rod of lordly might', it might be possible for you to use honey pot tactics to delay him, or get him off your scent.

Combo If you can steal what you need and frame the pirates, you're increasing your resources, and turning NPCs against other NPCs.