I noticed that when someone is stealthing and/or invisible, but walks on the dusty parts of the Underdark Tileset, you still get the dust appearing from the feet of where that person is walking.

Is this sufficient for a character IC to notice there is a person walking there? Or should we disregard the dust, and not RP having detected the stealth user unless we actually spot the other character?

Actually, you should only be seeing the dust for yourself, or if you spotted or heard the person. Are you certain you are getting dust on people you haven't spotted and/or heard?

Affirmative. I've seen dust many times before seeing the person standing there. ( I saw some dust and then I drank my see invis potion, and the guy appeared)

From my experiences, no, you don't.

There are the occasional strange and random dust clouds appearing out of nowhere on the ground with the Underdark tileset. This does not mean that there is an invisible/stealthed/DM/person standing there.

A mystery then...