Supernatural poker face
The first option seems to be: give immunities to important liars. But there are two problems on it:
a) Being immune to Detect Lies makes you automatically suspect of being a liar, just as someone with his face covered seems to be a criminal.
b) As more and more of your NPCs have that immunity, it won't be credible, especially if it comes from people without strong magic/supernatural background.
Increase the cost
This can't be done on all systems, but if you can it's not a bad choice. You don't forbid the use of the power, but you make it costly enough that players have to think twice when using it. You won't avoid them checking obviously important people, but you will avoid them scanning every single sentence a NPC says.
Make the use uncomfortable, or obvious
Imagine that you can magically check if people around you are lying. You would use it, right? Imagine that for checking them, you have to sit them on a chair and attach cables to them to monitor their vital signs. Would you still use it?
The spell could require a ritual as uncomfortable as that process. That would make it not suitable to all situations. But it will still be useful for others.
Alternatively, it may not be so uncomfortable, but rather obvious. Maybe the mage has to make magical signs with the hands, or look the suspect through a glass. Or the victim can feel the mind of the mage scanning him. Anyway, this will make the use of the spell rude on most social situations, as it would be akin to an interrogation.
If the characters don't have the right to perform such interrogations, the act can even be considered illegal. There's also a risk on warning the victim that he is under suspicion. An obvious detect lies spell is a quick way to make enemies.
Example: The Bone of Truth rite on Vampire: The Masquerade. Suspect must hold a bone, which will turn black if a lie is said. It is useful, but only on interrogations. You can't make an Elder hold the bone while you have a casual conversation with him.
Don't make the spell too accurate. Let the suspect talk, then inform the player things like: "he is hiding something" or "not all he said is true". That way, players will know someone has lied to them, but they don't know what is true and what is false, and anyway few people are 100% sincere.
If players want to be more specific, you can ask them to make several spell use, paying each time the costs. You can also improve the quality of the information with the success degree.
Train the players not to trust too much in the information
Related with the previous one, there are lies that hides truth and truths that hide lies. In "The Name of the Rose" inquisitorial interrogation, a man says a lot of truths on this fashion. I don't want to spoil the book, so I will make my owns:
I swear I didn't kill my wife. (True! He did kill his wife, but it's true that he swear he didn't).
I didn't steal the crown. (True! He paid someone else to steal it, then bought it).
I don't have the crown. (It's buried on some place I only know).
In the same way, there are truths that can be detected as false because of small lies.
Also, if someone has been fooled, or he is simply wrong about something, what he says is not true, but it isn't a lie, because he thinks it's true. If your players give it 100% credibility just because the spell, they will make a huge mistake. Better still, if the players detect a lie that is in reality a truth, they will be highly disoriented.
Design your adventures counting on the spell
At the end of the day, if you don't forbid the spell you must face the situation that your players will detect some of the lies.
Make it useful, but don't let it ruin your adventure. Count that the players will be able to detect lies, so don't give any lie the key of your adventure success.
The mastermind, the one who knows all the truth, can be someone hidden, operating on shadows. His servants won't know all the truth. Still better, they have been lied in several ways. Any interrogation will lead to true and false information, so the players will have to investigate which is which.
There are a lot of people that have been fooled by that villain (starting by his own henchmen, but the list can include some honest, respectable and good willing citizen), so their information is corrupted.
Some important communications can be written. Usually detect lies don't work on a letter.
If you allow the spell, don't make it completely useless. You can restrict it a lot, as seen above, but make it still useful or your players will feel scammed. Warn your players the spell have limitations (although don't explain everyone) before they get it.