There are too many situations to just have a sort of "set rule", though if you see a stealther, it's safe to assume you heard something. This does not mean you have identified them, as Strife pointed out, but you do notice something probably.
Everything I am about to write can be summed up like this:
If you don't know if you would hear them or not, use common sense, and as a last resort, send the sneak a tell.
-------------------------------------------------------------------
I'd like to make a note: You don't have to be in stealth mode to be sneaking! This goes especially for NPCs who technically NEVER sneak. What you DO have to do is check a few things...
A) Do they have cover? Then unless you can see through walls, you probably don't see them. Chances are you won't hear them either unless they're making noise for some reason.
B) Are they in armor, or are they talking? Then you might send them a tell asking them about it. Also, if they aren't moving, you PROBABLY don't hear them unless you have some rediculous Listen score. In that case, just send a tell asking if it's reasonable you heard them. Be reasonable, especially if they've put points into Move Silently and your Listen is still set to a whopping +2. "Being too busy IG" or "Not having time" to send a tell doesn't work, because if you're that busy, then you certainly aren't paying enough attention to hear someone stepping on the soft dirt roads, which leads to...
C) VERY important: Where are you? In the middle of Town Hall? If it's an invisible person running, then you can probably hear them. If it's a thief in stealth mode with invisibility during a fiery campaign speech, you're not going to hear it. In the streets? You probably won't HEAR them, but seeing them is probable, as long as they're walking down the middle of the road, again, for some strange reason.
D) Smelling someone is pretty crazy. Of course, some characters make special note that they smell bad. If that's the case, the sneaker should probably whisper an emote detailing that stench.
*emits a rancid odor, something akin to Mandarin Dreagle mixed with dead rothe*
Just my deux cents.
~Garem
ADDENDUM TO VESA: It sounds like you're describing a tunnel. Is there anything to hide behind? If not, after the first is probably fair. If so, it just depends on the corridor and/or size of the sneak, I'd say. And you can always ask them if they'll make a roll for you, you can counter with a Listen.