The task your NPC is attempting to perform, delivering a message to a party of adventurers in an unknown location, is difficult. The more resources they have at their disposal, the faster they can get the task done. I shall give options in order of increasing cost and speed.
Send messages everywhere
One option is to send messages to all major towns in the geographical region you expect the players to be. This option is relatively cheap because it requires no specialised skills for your messengers, so can utilise the normal 2 cp per mile rate (or whatever the cost of postage is in this part of the setting).
The message will then be waiting for the player characters next time they come into town. However, it is necessary for that message to be waiting for them. If it is necessary for the message to be private, then the messengers must be employed to hang around in town for a suitable period of time (maybe a tenday or two at 2 sp per day for unskilled labour) and wait for the party to deliver the message personally. Multiplied by the number of towns the NPC has sent messengers to, this could get quite expensive if there is high uncertainty as to the party's location.
If the NPC is willing to compromise the confidentiality of the message (probably okay if the message is "meet in ") and can rely on a bit of goodwill in the towns, a cheaper method is available. The messengers can leave their messages in a public place for the party to find. This may be on a notice board, or with a local barkeep or guard captain. Then fewer messengers can be used (since the same messenger can visit multiple towns) and the messengers don't have to be paid to wait around.
A side-effect of this method is that the party is likely to receive the message multiple times as they travel the region.
This method is unlikely to be viable if there is a very high uncertainty as to the party's location. This method may also be fairly slow, as the message is not targeted, and it requires the party to stop by a town.
Send a tracker and messenger
The NPC can employ a humanoid or group of humanoids to seek out the player characters and deliver the message. This is the method covered in guildbounty's and KorvinStarmast's excellent answers. It is, in my opinion, the most viable method given the circumstances.
The hardest part about delivering this message is that the party's location is unknown. However, unless the party has been deliberately stealthy, it should be possible for a skilled individual to track their movements. The tracker (who probably usually works as a bounty hunter or private investigator) would be given the message and as much information about the party as the NPC cares to divulge, with their last known location being the most important piece of information. The tracker would then go to that location, make inquiries, and follow the trail until they reach the party.
This won't be cheap. Skilled hirelings nominally cost 2 gp per day, but a highly specialised hireling such as this would likely charge more for their services. They probably have a flat fee for 'locate adventuring party somewhere in the North', which I'd spit-ball as somewhere around one or two hundred gp, rather than a daily rate for a task of unknown duration. But it would be reliable, or at least as reliable as the hireling.
Scrying then sending
If the NPC needs the message to be delivered within days (possibly today) rather than weeks, there are some magical options.
While there are no spellcasters available who are currently familiar enough with the party to cast sending, there is a way for the spellcaster to become familiar with the party if they have 5th level spell slots: by scrying on the party.
The NPC would give the bard, cleric or wizard a description of the party members. If the NPC has anything which once belonged to the party, or at the very least a likeness or picture of them, they would also lend the caster those items. Then the caster casts scrying on the party members. This casting of scrying is not guaranteed to work, as the party does not know they are going to be scried by an ally so they will make their saves normally. The caster repeatedly attempts to cast scrying until either a) the spell succeeds, b) the caster runs out of spell slots, or c) all party members pass their saves. If b or c, then the caster repeats the procedure the following day until success occurs (or the NPC runs out of money).
Once scrying succeeds, the caster is able to closely observe the party as if they were there. The 'familiar' clause in sending is ambiguous, but it would be reasonable for a DM to rule than ten minutes of close observation is enough familiarity for sending to work. (Since you are the DM, you are free to make that ruling.) The caster then casts sending, delivering the message.
This method is not cheap, and may not be available to the NPC. It requires a bard, cleric or wizard with 5th level spell slots, and will likely require multiple castings of scrying to work, occupying the caster's magic for several days depending on how good the party's Wisdom saves are. If you use this formula for estimating spellcasting prices, then each casting of scrying costs 350 gp, and the casting of sending costs 90 gp. The NPC would need a few thousand gp spare for this message, and good favour with a mid-level spellcaster.
Crystal ball of telepathy
The crystal ball of telepathy is a legendary magic item. It allows the user to cast scrying at will, and telepathically communicate with those it scries. The NPC does not require any assistance to use this item (although obtaining it is another story). The same issue of the party not knowing that the NPC is trying to scry them stands, so multiple attempts at scrying may be needed before someone fails their save (remembering that someone who passes their save is immune for 24 hours).
Change planes then gate
The 9th level spell gate (available to clerics, sorcerers and wizards, and also through the very rare magic item candle of invocation) can be used to reliably summon a creature who you know the name of to your location. If the NPC gets someone to cast this spell (or casts it themselves using the candle) and speak the name of someone in the party, then a portal will open connecting the NPC and the party. The NPC can then deliver their message in person.
One catch is that for gate to work the target must be on a different plane of existence to the caster. So before casting gate to contact the player characters, the NPC and their allied Tier 4 spellcaster would need to travel to any other plane, possibly via plane shift or gate. But if you can use gate, interplanar travel is trivial.
It is unreasonable to put a price on 9th level spells, so I won't attempt to.