Have you read the Supernatural Sense power in the powers section of the book? It specifically says "you must identify whether this is a purely mystical sense (using Lore) or a more physical sense (using Investigation or Alertness as appropriate)." All it's really doing is adding a trapping to either Lore or Alertness/Investigation (or in the case of detecting Lies, which is normally Empathy, it's moving the trapping to a different skill).
I have a police inspector NPC ("Inspector Sharp") in my game who can "hear truth in your voice" with his Supernatural Senses. I consider it a physical sense - he literally hears a different sound when you're telling the truth versus when you're lying. Mainly, this means he can roll Alertness instead of Empathy to detect lies. I suppose he could also roll Investigation to, say, track the sound of truth to someone who is talking nearby, but that's a little silly.
There's also the option of using the "too easy to need to roll" option with Supernatural Senses from time to time. For example, you don't make someone roll Alertness to hear their friend talking to them from two feet away. In the same way, if someone is telling the truth to Inspector Sharp, I usually don't make him roll anything, he just knows. But if they're lying, he should probably roll Alertness most of the time. There's also the situation where someone is telling the truth, but in a deceptive way (Faeries, lying by omission, etc.) - in that case, I would 'tell' Inspector Sharp (if he were a PC) that he's hearing Truth, then see if he wants to try an Empathy roll to pick up on the deception.
Note, also, that a character already should be able to roll Investigation or other skills like Scholarship to prove if something is true or false by actively looking into it. However, that method takes time, so the Supernatural Sense has a significant advantage in that regard.