You could look to Earthbound (US Title, on the SNES) -- In that system, enemies appeared on the overworld, dungeon, and sometimes town maps. Also, after you were sufficiently more powerful than the enemies in an encounter they would ignore you or even avoid you. You could make a point to fight them if you wanted, though. One nice thing about this is that it made grinding levels away a little less profitable than in random encounters -- Also, enemies that were sufficiently stronger than you would act more aggressively. Combined, this had the effect of your level being pretty predictable for the game designers, so the balance and pace of Earthbound always felt pretty good to me. When encounters happened, however, they took place on a traditional (Dragon-Warrior-style) battle screen, and the mix of enemies was representative of their over-world sprite, but there could be a mix, or other nearby enemies could join.
I personally like invisible encounters better -- Its just how an RPG, or at least jRPG, is supposed to feel. Surely I'm biased by the games I enjoyed playing back in the SNES jRPG heyday though. I don't think they break immersion, nor do I think that immersion is something to be chased, blindly -- The level of immersion and the way its manifested is a design choice like any other.
