This idea simply is so brilliant, I have no doubt about that it will be implemented if only someone gets to it.
Being able to see footprints and notice things disappearing are both classical ways of detecting invisible things.

I agree with this idea 100%. Also, as I mentioned in the Lighting thread, if an area is pitch black(not just dark, but complete blackness) nothing should be able to see, not even orcs/dark elves, but creatures could still detect via sound and such. Creatures such as snakes or bats would be completely unaffected by this darkness though.

As far as invisible things goes, I think that once you detect an invisible creature, either from it attacking you or whatever, a special symbol appears to indicate that creature. If you have poor perception it will disappear the next turn, indicating you lost it. If you have high Alertness, Perception and possibly Listening however, you will continue to see the symbol. You wouldn't be able to tell exactly what monster it is, but you will know a monster is there.

I support this. This makes sensing invisible creatures much more realistic and interesting. NetHack has a system almost identical to this. IMO the symbol for a detected invisible creature should be a grey ? sign - or any other colour except white..

More ideas: I think that this should work the other way, too: Monsters would gain/lose track of invisible PCs (except that a symbol will not be drawn, of course :P). If one has poor perception, there should be a chance to not detect the location of the creature. Lower chance to detect from a distance, like when someone shoots a missile or a spell at the opposite end of the room.

I like this idea.

Another way to notice invisibles: When a monster suddenly starts fighting with (or is attacked by, or otherwise interacts with) thin air.

Does this mean we have to implement a Smelling skill so you can notice those invisible ogre magi easier?

"A wafting stench of armpit odor and poor oral hygiene is carried by a gentle breeze from the north."

What happens if you are in a room with shifting breeze special message? Do you get improper scent directions?

What about in skewed perception rooms? Do you notice the footsteps on your right instead of your left?

I'll bump this now that invisibility and darkness have been implemented (though invisibility doesn't seem to do anything in 0.2.3).

The same code for gaining and losing track of unseen beings should be applied also for blindess and darkness.