A devious character understands their goals, their potential resources, their potential obstacles, and the incentives of any potentially-involved parties.
A devious antagonist is always focused on their goals, but they aren't necessarily directly pursuing those goals at all times. Instead they work to build their advantages up when opportunities to do so arise, with every step making their goals easier to reach.
I usually have the opposite problem: enough of my villains have ultimately been revealed to be devious enough that my players tend to assume any suspicious-seeming NPC is up to something, even if they can't figure out what that something is.
An NPC that is actually devious isn't simply one that commits itself to a dishonest or obfuscated strategy. An NPC that is actually devious is one that is ready to recognize and seize non-obvious opportunities and constantly builds their advantage until conditions are favorable for striking at their goals.
Goals are what the NPC ultimately wants to happen, but that the NPC for some reason can't accomplish immediately. There is nothing special about the goals a devious character might have relative to any other type of character.
Potential obstacles are the reasons that the NPC's goal is still a goal rather than an accomplished fact. These are usually where most of the deviousness lies-- the NPC needs to avoid or overcome the obstacles to accomplish the goal, and for some reason cannot or prefers not to do so directly. A devious character has a good understanding of what elements lie between their current situation and their goals, and why they make the goals harder to accomplish.
Potential resources are things or situations that the NPC can use to overcome or avoid the obstacles that are preventing them from realizing their goals. A devious character has an intimate understanding of what resources they personally command, and is creative and subtle about recognizing non-obvious possible resources and matching them against obstacles.
Incentives of potentially-involved parties is the glue that makes a devious scheme hold together when other people or groups are in play, and a devious character will work to align others' incentives in such a way that people pursuing their own (perceived) self-interest will also move the devious character towards their goals.
A competent, devious NPC will always have an as-comprehensive-as-possible current accounting of those four elements, will at all times look for opportunities to connect them together, and will never choose to allow obstacles to worsen or resources to be depleted to no purpose.
Thinking through those elements is how I get into the mindset of a devious character, both for laying their overarching schemes and also for having them respond to new circumstances.
When you say
On several occasions, I have tried to have an NPC dupe my players into being pawns. And every time, one particular player has caught on and turned the tables; in one case even double-crossing the guy. I don't mind my players succeeding, but in every case that its happened, I had much larger arcs planned, and they were short-circuited.
my first thought is that a devious NPC should never reveal, or allow to be revealed, so much of their plan that a player can catch on, and that same NPC should have strategies in place so that a PC catching on doesn't expand the PC's list of options and won't endanger the NPC's goals.
So the NPC's plan shouldn't be to tell PCs to "go steal a MacGuffin from X", but then give directions to Y instead. That's too easy for the PCs to figure out, and the solution is too obvious (scheme against the NPC with Y). That's not a devious plan, it's a simple plan with exactly one straightforward twist.
A devious plan would recognize that the PCs are both potential resources and potential obstacles, and seek to arrange matters such that the PC's incentives push them ever further towards being better resources and less effective obstacles. If the NPC has the PCs do something that would turn Y against the PC party (steal an irrelevant item, interfere in some plan) before sending them to steal the MacGuffin, then:
- The PCs' value as resources doesn't change (they can still be sent to
steal the MacGuffin from Y)
- The PCs' incentives are different than they were before (it'll be a
lot harder for them to team up with Y, if Y doesn't trust them and
starts working against them)
- Due to those different incentives, the PCs' threat as potential
obstacles is reduced (it'll be harder for them to betray the NPC to
Y, whether or not they discover the NPC's deceptions)
- The PCs have now been maneuvered in such a way their actions are more
likely to bring the NPC closer to the NPC's goal and are less likely
to effectively oppose the NPC
The specifics of how the NPC goes about this are mostly irrelevant. The deviousness is in working those four elements, and it doesn't matter if the NPC deceives the PCs about what they're doing, blackmails the PCs into knowingly doing what the NPC wants, or simply makes it unlikely and risky for the PCs to frustrate the schemes by collaborating with Y.
Manipulating any of those elements could be a minor story arc on its own, before the NPC sends the PCs to do anything that is even tangentially involved with their actual goals. And, crucially, the NPC will not willingly position the PCs anywhere remotely near their plots unless the NPC is affirmatively certain that the PCs can be reliably bent to serve the NPC's interests. The NPC will also keep tabs on the PCs to make sure they're not becoming more serious potential obstacles, and will be proactive in counteracting any movements in that direction.
tl;dr: A devious NPC will almost never set PCs on the trail of their actual goals, and will work to keep PCs from fully understanding the goals or the broader plans and situations around them. Instead the NPC will set PCs against obstacles the NPC has already perceived for other, plausible reasons, and will try to undermine the PCs' ability to act as obstacles themselves. Finally, the NPC will work to re-align incentives such that the PCs' self interest will at least seem to align with what the NPC wants, ideally to the extent that a PC figuring out what's really going on doesn't give them more scope or reason to do things that counteract the NPC's aims.