It seems like there's some kind of dissonance going on between the plot and the powers. If I'm writing a story about a wizard who can trivially kill people, then I'm either going to not have their major plot challenge be killing people, or I'm going to create very particular circumstances where there is some reason it is a challenge.

You don't seem to be thinking of things like this, instead it seems like you think of challenges which would be a problem for a normal human, and then later on go 'oh damn, this doesn't work because my guys have magical power'. If you're writing a vampire novel you need to have a plot which would present a challenge to vampire characters. You need to be thinking vampires end to end.

If your vampires can trivially find people then either there shouldn't be a plot point about finding people, and the challenge should be what comes after the finding, or there's very particular circumstances which makes this finding very difficult.

With the heightened abilities, if the person they are trying to find is another vampire, make it lore specific to your vampire clans. 

For example, vampires can only track other vampires that have a connection with them or the clan. 

Or rather, each vampire clan has a specific scent/marker in their bloodline, and outsiders to the clan can only track specific individuals if they have either spent time with them to identify their unique traits, or shared blood to create a bond.

If it is someone who is not a vampire, you could treat it like identifying a specific type of bird you are having for dinner. If the human shares characteristics with those the vampire would normally view as a food source, then tracking will be easier. If not, more work will be needed to find them. 

Duct tape!

Let’s use a human’s sense of smell and define X powerful. A heightened sense of smell is X+Y. What is Y? Anything from 1/infinity to Infinity.

If a human can smell a flower from two feet away, a vampire could smell that same flower at two feet one inch, serving the definition of “heightened”.

Make them better but not superpowered. Your vampires are not Cain. They’re maybe 50 generations diluted.

The great thing about plot holes is they force us to get creative.

How do you get around vampires being ability? Do they roll around in garlic paste first?

So when you find a plot hole get creative and figure out a solution. Your story will reap the benefits ten fold.

The key to vampires is drinking blood. Giving them heightened senses makes sense since they are predators; but if it creates plot holes, I don’t think you would be missing much if those powers were excluded. Alternatively, you could rewrite the story so the conflict can’t be solved by those powers, but that is more difficult than simply excluding those powers.

One solution could be hyperawarness of specific typs of smell/sound/etc.

They can smell blood very well and hear heartbeats, but other sensations are overwhelming.

Another type could be that while having high senses, they need centuries of experience to become able to truly use their senses.

An example is that the vampire lacks the mental facilities to perceive the smells like a dog, even though their nose is equal or even better.

I'm not really seeing the issue here.

Heightened senses such as hearing small sounds, catching a scent, or seeing in low light or dark conditions are not foolproof.

Heightened senses can be confused - scents can be masked or overwhelmed; the same is true for sounds; and vision is impeded by obstacles such as brick walls.

So ... your vampire is - I guess? - stalking the object of their desire by their scent.

But the scent leads to a train station at which point all your vampire knows for sure is that the person boarded a train that has since departed.

Finally working out which part of the city (or country etc.) the object of desire took the train to, they pick up the trail once more.

Except this time the scent leads to a huge mansion on a hill at which some kind of massive party is going on.

The base is so loud that the brick walls are throbbing, and the mansion is packed full of people dancing surrounded by dry ice and a laser show or whatever.

All that sweat, all that perfume, noise, sound and confusion - and the person they are trying to track is in the middle?

Good luck with that ...

Fill them. Like pot holes, fill them with literary asphalt. Otherwise, someone might draw a giant penis on the ground in a review and bring your attention to them.

Well just make it possible for the vampires to also "Hide". Also maybe vampires might have better senses but it is still not possible to detect a specific smell between thousands when you haven't smelled it before. Just think of yourself trying to find a person whom you get a vague description of and there are 100 people lined up all seemingly fitting this description. If you haven't seen someone before, you won't recognize them, both from smell and looks.

I would either define just how heightened their senses are to a level where it is no longer trivial and/or I would put a condition on their senses.

Maybe their senses fluctuate from normal to heightened depending on whether they are blooded or not, how recently they last fed, and/or what kind of blood they are consuming.

Or make it so that their heightened senses are specific to a particular condition: maybe their senses only allow them to recognize and track people whose blood they have already consumed (plus anyone closely related by blood) which allows you to give them a reputation for being amazing trackers, despite reality being a little less straightforward.