L5R has the most specific example in my immediate memory. In one game, the players were in a diplomatic situation and a Shosuro Shinobi (ninja) was sneaking around to stir the pot. This was a starting level game, and some of the players had not taken Investigation (and thus couldn't explode their rolls for being untrained). Even at a rudimentary level without increasing anything the Shosuro would easily beat every roll the party made that didn't have a void point backing it. Therefore the players felt like they had no chance at winning.
Now, I run a fairly sandbox world and for players not in the know I throw out overt "don't poke the bear" warnings and remind them that min/maxing their characters can leave them open to just such an attack. However, I don't use them because the players don't really get to do anything, but I want to incorporate ninja\shinobi that are more than just random dudes and dudettes in black PJs.
Sometimes the bad guys would realistically send some skilled and sneaky assassins against the PCs and by the rules it's hard to see how they wouldn't easily succeed in wiping them out.
TL;DR
How can a GM use competently undetectable characters as antagonists without it being perceived as unfair to the players?
Best Answer
Make sure the assassin is warranted. Some previous player behavior should have warranted someone coming to kill them. Note that this doesn't have to be for notorious reasons; a do-gooder with enough reputation could become a target for assassination.
Drop hints that assassins exist. Perhaps the assassin scouts the party in a bar, interacting with them enough to gauge their strengths/weaknesses. Have the PCs encounter assassinated NPCs (maybe killed with a specific, rare poison). Put up rewards to catch the assassins.
You want some clues that something is going on, to give the players a chance to prepare. Speaking of which...
Is the party keeping a watch? If they aren't setting their own guards, barring the door, or setting a magical field of protection, they're practically asking to be assassinated. If not, consider having an inept assassin fumble the job first to get them on their toes.
Make sure to follow the games rules for surprise attacks. Most systems have some ability that allows you to detect a surprise attack, and get at least a partial reaction. Don't deny the PCs their listen, spot, notice, etc checks.
Finally, be prepared for success. A player may be frustrated if their character dies, but don't just leave them to roll a new one. Have an NPC available to perform a resurrection (for the right fee), and consider letting the player play an NPC while his character is dead.