So basically my level 20 party have managed to run afoul of a very dangerous assassin who has attacked them several times, but always gets away if things turn against him. In our last session, they managed to find out that he was actually masquerading as one of the crew members on their ship. The assassin immediately escaped into town to plot his next move, but one of the party clerics summoned a planar ally and asked them to track down this assassin and bring him back to the party.

So there's no exact celestial creature that seems especially good at tracking (that I've found), the spell doesn't give me any specifics of what the celestial should be and the assassin is a high level enemy (has to be to have any chance against the high level party) who is really good at hiding and is strong enough to very potentially take out the celestial that's sent after him. 

Thus, I'm not sure how I should rule this. I have some ideas - for tracking I could have them make a series of contested skill checks or a series of skill checks with set DCs using the planetar's stats for tracking at least. I could stretch that and say that the rolls could be used to decide capture as well, but that feels a bit like I'm stretching it. I don't want to just rule it the way I'd like, because I'd rule it the assassin gets away, but that feels unfair to the party.

Has anyone encountered a situation like this (or had trouble trying to rule how planar ally works) and/or have suggestions on how I could/should rule this?

for one thing, this single mortal is troubling a group of essentially demi-gods?? they might not see themselves as quite THAT exceptional, but let's for a moment think in those terms: this is a favored of the gods asking a powerful leader of another realm to track a mysteriously powerful creature. these are the big leagues. so, what if this resourceful assassin already has influence over some higher-up celestials. like a sort of "i can't be your lawyer because your opponent has already retained my services" sort of thing. it'd be boring to just dead-end so quickly, so perhaps there's some backroom dealing going on. yes, the celestial ally will seek to fulfill the letter of their contract, BUT they're technically also in contact with other lesser celestial beings who are not bound. they don't have to tell these lesser beings directly, but they'll know to go forth to obscure any trail so that the first celestial is guaranteed to find nothing when they arrive.

the characters could even catch glimpses of clean-up crew fleeing with brooms and a shoe. if the ranger sees tracks, the planar ally announces they will accept to follow those footsteps only after first investigating possibility of subterfuge by sweeping the area until they circle back to the first tracks... to find none there. if the wizard detects magic, perhaps the faint trances of a rope trick or dimensional door, then the celestial's secret helpers will bumble across the area until it's a wild magic mess that begins to attract stray fey beings which only further obfuscates things. has the assassin done some job for the celestials that they'll do anything to keep secret? are they (lawfully) bound to some contract that they'd actually be very grateful to be freed from? are they simply afraid they'll be hunted down if they defy the assassin?

What did the cleric negotiate for the payment? Planar ally doesn’t give you a hunting dog that obeys your will, it gives you a potential ally that may or may not help you if you are willing to compensate it properly. What are the players offering in exchange for this angel’s (or whatever it is) services? Angels are busy creatures. It could easily decide it doesn’t have the time for something this trivial. 

Assuming you are past that part. You should absolutely just decide what happens without rolling. It’s all happening off camera, anyway. Figure out an option that’s best for the story and say that’s what happens — don’t let the dice make story decisions for you when it’s all npcs interacting. I agree that the angel just coming back and saying they couldn’t find the guy is going to be unsatisfying. So, maybe the assassin just kills the celestial. If the bad guy is a challenge for a whole party of level 20 PCs, it can certainly take out some CR 10ish creature. Just say the angel leaves to do the job, and it never comes back. Now they still have to hunt down the assassin, and they’ve probably annoyed their god for getting one of his servants killed. They whole thing becomes a plot hook.

Get a wizard.

Demiplane + Gate.

Problem solved.

There's a few options which really depend on if you want it to work or not. 

• the being they beseech may simply say it is beyond their power or they wont interfere. They may need to ask a different entity one more associated with tracking.
• The couatl has access to scrying so they can perhaps try to track the creature that way. It may take it multiple attempts and they may need to try and find something like an item belonging to the assassin to make it easier.
• You give them a celestial to search the area from the sky. For example a Pegasus that they can ride or a swarm of birds 
• pick a different stat block and call it a celestial for example a wizard with divination spells or a tracker
• The celestial may simply come to assist with combat or travel, or act as a look out to give a warning for the next attack.  the Hollyphant or [monster]unicorn[/monster are good utility allies with healing and teleportation.

also like others have said since the assassin is willing to take on multiple heroes of legendary status they should probably be pretty powerful and notorious themselves. So most likely capturing them would just result in the players having to fight them as the assasin quickly escapes. 

Planar Ally is weird; in prior editions it had a hit die limit which would have made it pretty clear that this plan is a nonstarter, but 5e doesn't put any real limits on the spell.

I'd be tempted to just send them a reskinned Invisible Stalker, as its well within the reasonable limits of a 6th level spell and actually has appropriate capabilities, though the assassin may well plane shift (rope trick, etc) to evade it. Or just kill it.

Quote from Pantagruel666 >>

Planar Ally is weird; in prior editions it had a hit die limit which would have made it pretty clear that this plan is a nonstarter, but 5e doesn't put any real limits on the spell.

I'd be tempted to just send them a reskinned Invisible Stalker, as its well within the reasonable limits of a 6th level spell and actually has appropriate capabilities, though the assassin may well plane shift (rope trick, etc) to evade it. Or just kill it.

 yikes! a celestial invisible stalker! i don't know why, but that sounds strangely amazing. even so, that doesn't sound very... celestial? however, what if that's the point. what if some summoned unicorn is giving sly vibes and says they can send some friendly invisible assassins after the mean mortal assassin no problem and for nearly free. just give the word, chum! that would ping my player radar that i'm stepping into something i don't understand. what if your party is authorizing a strike into the territory of an enemy these celstials have wanted to start a war with for years? or what if the assassin can simply charm the creatures into assassinating stuff for him? what if the assassin is the one who was charmed, only a puppet themselves? what if the only evidence we found was three black hairs on a pillow... which scrying (if it isn't blocked!) might indicate are from the head of three different kings?

Quote from rumloverum >>

Quote from Pantagruel666 >>

Planar Ally is weird; in prior editions it had a hit die limit which would have made it pretty clear that this plan is a nonstarter, but 5e doesn't put any real limits on the spell.

I'd be tempted to just send them a reskinned Invisible Stalker, as its well within the reasonable limits of a 6th level spell and actually has appropriate capabilities, though the assassin may well plane shift (rope trick, etc) to evade it. Or just kill it.

 yikes! a celestial invisible stalker! i don't know why, but that sounds strangely amazing. even so, that doesn't sound very... celestial? however, what if that's the point. what if some summoned unicorn is giving sly vibes and says they can send some friendly invisible assassins after the mean mortal assassin no problem and for nearly free. just give the word, chum! that would ping my player radar that i'm stepping into something i don't understand. what if your party is authorizing a strike into the territory of an enemy these celstials have wanted to start a war with for years? or what if the assassin can simply charm the creatures into assassinating stuff for him? what if the assassin is the one who was charmed, only a puppet themselves? what if the only evidence we found was three black hairs on a pillow... which scrying (if it isn't blocked!) might indicate are from the head of three different kings?

 You can just make an angel appear that turns invisible or do something like the last lines of the little mermaid book and have divine spirits of the air. 

Quote from Solarsyphon >>

Quote from rumloverum >>

Quote from Pantagruel666 >>

Planar Ally is weird; in prior editions it had a hit die limit which would have made it pretty clear that this plan is a nonstarter, but 5e doesn't put any real limits on the spell.

I'd be tempted to just send them a reskinned Invisible Stalker, as its well within the reasonable limits of a 6th level spell and actually has appropriate capabilities, though the assassin may well plane shift (rope trick, etc) to evade it. Or just kill it.

 yikes! a celestial invisible stalker! i don't know why, but that sounds strangely amazing. even so, that doesn't sound very... celestial? however, what if that's the point. what if some summoned unicorn is giving sly vibes and says they can send some friendly invisible assassins after the mean mortal assassin no problem and for nearly free. just give the word, chum! that would ping my player radar that i'm stepping into something i don't understand. what if your party is authorizing a strike into the territory of an enemy these celstials have wanted to start a war with for years? or what if the assassin can simply charm the creatures into assassinating stuff for him? what if the assassin is the one who was charmed, only a puppet themselves? what if the only evidence we found was three black hairs on a pillow... which scrying (if it isn't blocked!) might indicate are from the head of three different kings?

 You can just make an angel appear that turns invisible or do something like the last lines of the little mermaid book and have divine spirits of the air. 

the link for the invisible stalker includes an illustration which lends the creature a sinister "climb down your throat and stab it's way back out" sort of look. i think that's where my imagination went, but yeah angels can be good too.

anyway, however it goes, my vote is for letting the situation add to the plot rather than shortcut it like Data in that one TNG episode where he's trying to figure out the appeal of Sherlock Holmes (S2:E3) and just skips to the end: "you mean this guy?" *shakes the culprit by the collar*

Thanks everyone for your advice and suggestions. It worked out.