Just have certain areas in the wilderness set as PVP zones. Set them far enough away from the roads and cities so that someone can't just accidentally walk into them, but so that they are potentially in the path of the quickest route between cities. So, if you were to run in a straight(ish) line from, say, Ojaveda to Hydlaa, completely ignoring the roads, you run a risk of being killed along the way. This would have the added benefit of more player interaction on the roads.
Another good but questionable idea is to add small PVP zones into cities, for example the hidden alleyways and sewers, but tucked far enough away from places where beginners might go to train or quest. I swear that these at one point existed, but were rare.
As for making PVP worthwhile, we know for certain that we will never allow players to loot other players, so I propose this: allow stealing from other players, but only conditionally, and if the victim chooses. Assume that a player has been beaten or has yielded. The attacker can either kill the victim, let them go, or steal. The victim has a choice to offer something for their life. You'd need a longer wait period between losing and release, but I think this should only apply to PVP zones and be five minutes maximum.
Final idea (I swear), which I think would really help roleplay and tie into mechanics, is to make faction-based PVP. This is drawing from Dark Souls, but I could see it working really well here. Once you've joined a specific faction, a Dakkruist one for example, killing people could reward you with more faction rank but additionally give you points that you could exchange for money or items with an NPC in the Death Realm. Another (legal) example would be a gladiator faction, which gives you a point upon defeating another player in the Arena, and those points can be redeemed for money at an NPC in the Arena.
Tell me how all this sounds, because I'm pretty sure these ideas would save PVP. We need to make PVP great again!