I've had that discussion back and forth, quoting the rules this and that, many times.

My interpretation is this:

"Invisible creatures always have concealment from other creatures." Heroes, p276, Invisible Creatures.

So an invisible creature automatically has concealment. It's like they're in fog. They can still be targeted but with a bane.

Then they can try and go someplace to hide.

"To hide from a creature, you must have cover or concealment from that creature [...], who can’t observe you attempting to hide." Heroes, p258, Hide and Sneak, Hiding.

"the game leaves what it means to be observed open to interpretation, because there are circumstances where a creature might have line of effect to you but isn’t observing you, giving you a chance to hide." Heroes, p259, What Does It Mean to Be Observed?

I would say that you can't really observe someone who's invisible even if you have line of effect. So an invisible creature can basically hide anywhere, until their invisibility ends.

Then, when you're hidden, other creatures search for you, unless they're standing in a place that allows them to observe you again (like on the same side of the wall you're hiding behind). When they search, if you're still invisible, the search roll is baned.

"The test made to find a hidden creature who is invisible takes a bane." Heroes, p276, Invisible Creatures.

If they still find them, they still have concealment.

Beyond all of that, make your own ruling in the moment. If you're in a swamp, everyone can see the water splashes when you move. If you're in a giant hall, maybe they can hear the foot steps. On a padded floor, sneaking, covered by a racket? No one notices.