How do I find this relic - is this a bugged quest?

The item you are tasked to find is probably in the inventory of an enemy hero, the quest marker points to the hero.

This was on the 5th campaign first map and it was pointing to an empty place - no enemy heroes there

I don't recall any quests being bugged and I spent countless hours playing W3.

But if you think the quests is bugged just set the quest aside.

I think it might be. I just got the same quest. The relic I am supposed to find is the Axe of Slaying, but it's not there. I reloaded from my save... a few times because I was seeing if it would eventually give the same quest. It did, same Axe. I covered every hex in the area, each time looking for "items on the ground" and it was still not there.

Some heroes can be invisible, or could be vectoring between two cities and be off-map until they arrive at their destination. Also, some ruins are hidden, and may require you to take several steps in their vicinity to be discovered.

Bu if it's none of these things, it's most likely a bug and you should abandon the quest.

I've encountered this bug during campaigns, too. The "quest arrow" is not pointing to an enemy hero, but rather a ruin that's already been explored. I had to set the quest aside.