Here are several general things. I will talk specifically about your game later
Empty threats are not useful.
Here is the thing, threat are effective when the threatened party believes they are real.
If the party does not respond to threats that way, they likely do not believe anything would happen.
It is important for the players and characters to understand that there is weight behind the threat. Show that the NPC means business and remind players of it. This can be as simple as "You remember X that happened" (for anything the character is sure to know) as an in-game reminder or even out of game "Do recall that few sessions ago X happened". Do not shy away from bringing it up out of game - it is entirely possible that players forget details. There are days, if not weeks between sessions.
NOTE: This does not necessarily mean that the NPC has to act against the party. It could as effectively be the party observing an interaction where the NPC was following up on a threat. Or they can see examples of the results of threats:
The baker the party meets every day is now limping. When asked, he explains that he owed some money to Bigbully Meangoblin - the local mob boss. The baker further says he got off lucky - he heard of that store in the other side of town. The owner loudly refused to pay for Bigbully's "protection". A week later the shop burned down with the shop owner and his family in it. So, the baker is grateful that Bigbully was generous enough to give the baker an extension on the loan. The baker finishes up with a trembling "Do...do, you want to buy some f-fresh bread?"
Death is cheap in D&D
By extension physical violence, is cheaper. If players lose HP, that is maybe some health potions or a couple of spells. Or they can always rest, too.
Death itself is a running joke in D&D - at most it costs some money to resurrect a player. But even a lower-level Cleric can cast Revivify on a recent corpse.
In some games, the attitude swings too far in the opposite direction - death is ever present and characters can die at any point in time. Maybe even multiple times in a session.
That is certainly not the attitude in all games. Death can be serious and meaningful. The point is that it can also be a very cheap way to threaten players. The response can just be "Eh, I will just have to pay for resurrection" or "Eh, I will just have to roll a new character again".
Simply put, threatening with death should be used sparingly.
The joke is that players fear for their items or levels more, as those are harder to come by. Hence why things like rust monsters or negative levels (in older editions) exist. But this is a cheap way to scare players. I would not recommend it. It might work once or twice but, especially after being used multiple times starts to lose any punch. Depriving players of that magic armour, or magic hat, or magic sword, etc. works only so many times.
Death is not realistically portrayed
This is related to "death is cheap", however, I feel it deserves its own point.
On one hand, death for player characters often enough does not carry enough weight. However, NPCs often do not pay it much attention. A typical encounter would have the player characters pitted against bandits, or town guards, or evil cultists, or any number of creatures that should value their lives. But the encounters usually end with the players killing each and every enemy.
Let's think about this for a moment: a group of bandits is just some people who rob to provide for themselves. Realistically, if half the bandits are slaughtered, why would the rest want to go to their death? Yet, a typical encounter would end up with all the bandits dead. As if they all do not fear that end.
Yes, some NPCs might be inclined to give up their lives. However, the point here is that if NPCs players encounter do not put much value on their life, why should the players put any value on theirs?
There is opportunity to change how NPCs behave in a fight. The ones that are intelligent enough should give up and beg for their lives. Especially if their boss, or some of their friends/colleagues, or the boss's underlings were already killed.
The reaction of NPCs towards killing might need to portray the seriousness of it in order to convey to the players what the stakes are.
Player investment
There is another aspect entirely - are players even invested in the game? Some people play the game just as a fun getaway. Not paying much heed to what is happening in game. You might expect that when a character is faced with a threat, they might respond seriously. But the player might just not be thinking about that, if they are not invested in their character.
There might be some alternative - find what the player is invested in. Maybe it is the story. It might be a character in the story. Or a particular goal. Threatening what the player (and thus by extension, the character) does care deeply about can be more effective.
NOTE: This should also be used sparingly. It can come off as heavy-handed and can cause a problem for the player's enjoyment of the game. Maybe make sure they are OK with this if you are not sure how the player would respond. Take great care with characters the player might be really invested in.
One less-problematic way might be to just threaten the goal of a character. A player might be trying to get some item but the NPC can try to deny them that. If the players want to get in the good graces of the king, then an NPC who has contacts might threaten to spread bad rumours about them. In general, that would undermine the effort of the player characters.
It can work better as a threat because it poses a direct obstacle to something the players are working towards. And it introduces a more interesting story element. Moreover, it allows players to fail more gracefully - even if the threat is followed up upon, the players can still achieve their goal. They now have a new villain. The item they sought is just now in that NPC's hands and it can be dangled as a carrot to get them to do what the NPC wants. The players can work with the NPC or plot to defeat them. In either case, there is potential for more story. And eventually the goal of "get the item" is still on the horizon.
Embrace consequences
Threats can be issued and players can choose to ignore them, even if there is weight behind this.
This can be even more general - never expect the players to act in certain way. Whether through in-game intimidation, cajoling, begging, contracts. Players can always ignore those and end up going against what they were "supposed" to do.
There can be consequences and they can be weaved into the story. The players might decide to pay no heed to the "warnings" they are given by that criminal and if something bad happens it should not just be a background detail. Whole sessions or even story arks can spring up from such an action.
One way to show you mean business but without imposing hash consequences yet would be to play out a "what if" session. You can announce it ahead of time or keep it secret until after. In either case, essentially the players will see how things play out for the worse. This can be a dream, or a vision of the future, or just a quick one-off with little justification. The point would be to show what could happen if the players do not act how "they should". If the players confirm that is indeed what they want to do, then everything that happened in the session actually happened. Just jump to the time after it. If they decide to amend their choice, then you can still jump ahead and assume that they help up what they wanted.
This can be an effective technique if used well. It should be introduced early to show what kind of game is being run. The best place to have one is after a meaningful choice that can have real consequences for the rest of the game. It is also useful for newer players.
Most definitely it should not be used multiple times. "It was all a dream" already has a bad reputation at undermining the very meaningfulness the "what if" session is trying to establish. To that effect, I would advise to announce it beforehand, as well. Yes, maybe it seems more fun to reveal at the end that it is not too late to prevent this, however, it can also leave a bad taste in one's mouth.
The way I would set up and run such a session is to leave the players with a choice at the end of a session. For example, the evil vizier wants the players to accept his offer and aid him, or else. Session ends with the characters pondering their choice. I would discuss with the players what they want to choose. And if they say the "or else", then I would tell them that next session I would run a "what if" and at the end they can choose to embrace it or change their choice. The session starts, and the players having rejected the vizier's offer find themselves blamed for a crime they did not commit. On the run from the law and nobody around wanting to give help to outlaws. Even friends, acquaintances and family shun them for the heinous act. Perhaps the players like the struggle against injustice. The session after the "what if" continues where the last one left off. Or perhaps they re-think their choice and prefer to work with the vizier. For now. So the session after the "what if" has them running an errand for the vizier.
Discussion, discussion
As always, there can, and probably should, be a frank discussion with the players. What their goals and expectations are of the game. Maybe they just do not align with the game you are trying to have. Or maybe both the GM's and the players' intentions align but a given intimidation attempt did not come off as it should have.
My feeling is that the players aren't intimidated even though their characters would be.
I do want to address this. No, the characters need not be intimidated. You had the characters threatened with physical violence when they were weak. Potentially death. That is effective...for literally just that one moment. Let me put this into perspective: player characters face physical violence, injuries, and death very often. D&D is a game built around the concept that player characters would be doing a lot of fighting. In-game, adventurers might be brushing with death every day. Maybe even multiple times a day. Every encounter they fight for their lives. If they are downed and start making death saves, they stand at death's door. Only to rest and repeat this over and over.
Why should they take into consideration the threat from the past? The NPC has advantage over them now but tomorrow after a long rest, they would have full HP and other resources. That is not "metagaming", it is perfectly normal for adventurers to think this way in-game - they do long rests all the time.
Quite honestly, the threat does not make much sense. "I could have killed you but did not" does not really carry much weight as a threat when the party stands fully prepared later on. Especially if the threat came at a point when the characters are weak. It comes off as if the NPC cannot back up that threat otherwise.
This, of course, comes with a caveat - depends on the type of game. But the most regular types of D&D game, there is not much logic to keep being in fear after the NPC leaves.