You need to understand that Diplomancy is a powerful weapon, and take active measures against it
So, a 29 is a very bad Sense Motive check to be expecting going into a meeting with a powerful enemy liar. Any Diplomancer worth their salt is definitely going to be subject to glibness when it matters, and that alone is a +20 bonus. A 29 isn't terrible-- it'll keep the devil from repeatedly telling you impossible things and forcing you to believe them, probably, because that would take at least a 49 and that's a pretty decent target for a low-level bluff-based BBEG, but it's definitely not going to keep your whole party safe from a dude who's whole deal is messing you up with social checks. No, for that you need a better plan.
So, first of all, you should never let someone you know has a massive Bluff score talk to the party. Just don't listen, don't give them space to talk, carry thunderstones if you have to: do whatever's necessary to keep them from getting to make a Bluff check. In this case that means when you show up your party should all be deaf and probably subject to telepathic censure or similar. You should then beat the devil unconscious, tie it to a chair, cast dominate monster or some other form of magical compulsion to force it to be truthful or to rip the knowledge directly from its mind and/or corpse, and only then allow yourselves or better yet a trusted specialist or expendible guinea pig to handle the information in question.
Alternatively, you can try to have a meeting with the devil. You should not be rolling sense motive during that meeting, and the devil should not be rolling Bluff. Either of you, of course, could break the rules at any time and bust out your social skills, in the same way that either of you could pull out a plasma rifle and unload a full clip of ammunition into the other. You don't do that, though, because people who sneak attack the other side during a parley don't live very long and can't expect others to honor their parleys in the future. Besides, you can have someone not attend the meeting so they can solve the problems if it goes badly, and you can probably have your sense motive dude bust out the weapons if the devil busts out a Bluff check.
Social skills in Pathfinder (and D&D 3.5 to a lesser extent) are not so much abstractions of how real in-character social interactions should go as weapons that affect the targets' minds rather than their bodies. Bluff is mind control, just like dominate monster or modify memory or-- most similarly-- 3.5's mindrape. Your party should regard it as such, and be extremely cautious around creatures who are capable of using it effectively. Just because PCs get carte blanche immunity to Diplomacy checks does not make them similarly immune to Bluff checks, and they should not underestimate the danger enemy Diplomancers pose.
If this bothers you, you may wish to suggest to your DM that mind control not be included in your Pathfinder game, including extreme uses of the Bluff, Diplomacy, and Intimidate skills. This is a fairly common house rule across 3.x games and in my experience it has worked fine though it does significantly change how the game is played and also limits the total dominance of magic-users over their mundane kin.
But what are the technical limits of Bluff? Am I actually worse off calling for a Sense Motive roll?
There are a couple of limits to what you can forcibly change in a character via Bluff. Specifically, bluff allows you to cause a target to believe any specific thing:
with a successful check you convince your opponent that what you are saying is true
Unlike many other skills, there is a maximum to how hard the GM is allowed to make a Bluff check for you:
Note that some lies are so improbable that it is impossible to convince anyone that they are true (subject to GM discretion).
and from the table:
Circumstances: The lie is impossible Modifier: –20
So you can know that if you roll 20 points higher than a target's Sense Motive roll you can generally make them believe anything you want. If your bluff total is 39 higher than a creature's Sense Motive total, you can generally make them believe whatever you want all the time with no chance of failure. I say generally here because there may be other circumstantial or feature-based modifiers to this DC (most notably the modifiers found in Ultimate Intrigue), but the point stands that with enough Bluff you can convince anyone of anything. "These are not the droids you are looking for", for example.
You can also use Bluff to replicate telepathy, making a trivial DC 20 check to force a creature that shares a language with you to receive a message and using that check's Bluff result to prevent anyone else from being able to discern your true meaning without a superior Sense Motive result. This lets you make your Bluff "you believe this now" statements secretly, among other things.
You can also use Bluff with Diplomacy to convince people that your Diplomacy use isn't actually happening and the 'requests' you are making of them were their own idea in the first place.
You can use Bluff to convince people as a group not to pay attention to you, though not usually the inverse, to roll initiative in duels, and for many many other things you purchase for the skill with feats or traits.
You cannot use Bluff to oppose active uses of the Sense Motive skill the same way that skill is used to oppose active Bluff checks, except via the feat Veiled Contempt and even then you may only add twice your Bluff ranks to the DC. That said, a player calling for a Sense Motive check can learn from it only that the target is generally untrustworthy, not that any specific statement was a lie, and the 'hunch' so gained does not free them from the damage done via being lied to. Bluff is always used v.s. Sense Motive, but that's a separate check from the one that is used when a player calls for a roll.
You cannot use Bluff to make a request of a character nor to suggest a course of action, except as a modification/enhancement to your Diplomacy roll. Diplomacy does not work on PCs, so you can't have your PC's attitude altered that way, nor can the devil force you to comply with requests it makes that way. You can only use Bluff to force PCs to believe false information, not determine what they do with that information. The Intrigue rules go into this in some detail:
Bluff Doesn’t Define a Response: Even the most successful lie told using Bluff doesn’t determine the course of action the deceived person takes—it just primes the target with misinformation.
Unfortunately, the intrigue rules do also suffer from several contradictions with the CRB, particularly with regards to the limits of the Bluff skill, and so depending on which source your group regards as more authoritative your play will go differently there. None of the rules in Intrigue prevent Bluff from working as it otherwise would categorically, they just let the GM forbid the player from succeeding at some kinds of checks by saying that impossible should be changed to 'almost impossible' or that alternatively success could sometimes just means the NPC believes that the PC believes what they are saying, rather than believing the proposition put forth, etc. Essentially it provides a lot of ways you could change the Bluff rules as a GM if you wanted to to make the players less able to use them without disrupting the ability of NPCs to use them if you don't like that PCs can convince NPCs of crazy stuff.
So, in conclusion, as regards technical stuff, the devil should have rolled Bluff as soon as he was lying to you if he wanted that lie to have the force of a Bluff check behind it. If he did, it would automatically be against the Sense Motive check of his target, and he would need a separate Bluff check for each member of your party and the conversation would take at least several rounds instead of a couple of free actions. It is totally reasonable, however, that your party would, if it stuck around for those rounds, become convinced that the MacGuffin was located in the pit of deadly death and that not swan diving into said pit would result in your being cursed with seven years bad luck.
Your later, active, sense motive check would be entirely separate from that. It would tell you, barring abilities the Devil had to the contrary, that the devil is not a trustworthy fellow and also something is up. It would not tell you those things you had been convinced of were false, and it would not tell you that the devil was the source of those ideas if the Devil had caused you to believe those things subtlely. You, then, would decide what your characters do, which could include being pretty sure the stuff they believe is wrong, killing the devil, and running away to try and process their cognitive dissonance. It could not, however, include no longer believing the things they have been convinced of-- even if they suspect they might be wrong-- without "new information that allows them to realize the truth of the matter" (again from the intrigue rules).
In short, you are not worse off calling for a sense motive roll except that that means you have to be around a Bluff user for a full minute of time. Your sense motive roll is not opposed by the target's bluff check, but it doesn't let you know if any particular statement is a lie-- that's your passive Sense Motive roll you make in reaction to being Bluffed at.
As you note, if you already know that a target is untrustworthy and using Bluff, then Sense Motive is only of use for you as a meagre defense against their persuasive abilities. Instead, you shouldn't be talking with them unless you can guarantee that they are not going to use social skills. In your description of your game this seems unlikely and so a violent solution where the information is forcibly obtained is probably expected.