I'm starting to think that non-random battles, as much as their's a trend against them, aren't that great for games where you have very, very separated combat and exploration phases.
Look at it this way.
You're in a dungeon with ten encounters in it, and you can see the enemies on the map. There are basically two ways this can play out:
1) You can walk past the enemies since you can see them.
2) They're all mandatory encounters that you can't get past in which case they're not really functionally different from random encounters.
(2b. This is actually pretty common in older PC dungeon crawlers, but you have non-random points where you MIGHT get an encounter, but whether you get one or not is random).
I'm going with point 1 here since it's more interesting from my perspective and I've got two or three really big problems with it:
1) Assuming enemies are avoidable, they probably either chase you or have some sort of pattern you can learn to avoid them. If they start chasing you and you want to avoid them, there's a good chance you have to backtrack across the map some to avoid getting attacked. If you still get attacked, you now have the added time from getting chased around combined with getting attacked. A random battle, in the last case, would've been faster.
1b) Dungeon Master-type games have a subset of this issue, where you need to back up constantly while your weapons recharge, although this is more of an issue with the battle system. Also their battles tend to not actually be avoidable since you can't run past enemies and they tend to get you at chokepoints.
2) If battles are readily avoidable and you avoid a lot of them, there's a good chance you're going to end up under-leveled. I think a lot of players just end up doing every battle, whether they're avoidable or not, for this reason. Which raises three issues:
a) Why even go for non-random battles in the first place if the player's going to be compelled to fight them all anyway?
b) If there are ten encounters in an area and you're going to be compelled into doing them all, it gets back to that checklisting thing again -- you're not playing, you're just checking semi-mandatory tasks off a list.
c) Finally, if you still have bosses that expect you to be at a certain experience level, but all non-boss combat is not required, then all non-boss combat is effectively grind.
Point c in particular is something I'm running into in Persona 3 a lot since it's really easy to avoid fights.
3) I don't see this much so it doesn't really bug me, but whether you have random or non-random encounters or not does impact how you design areas. You will tend to get larger dungeons with more empty space when you have to account for non-random encounters, just because you have to make room for more map entities.
I'm trying to think of cases where random battles really bugged me and like, it's Rogue Galaxy and Xenogears that are the biggest offenders. And in both cases it wasn't the random battles per se it's that you can fall off the fucking map when they hit and you have these goddamn jumping sequences in XG and thse goddamn inavigable multi-layered prisons in Rogue Galaxy. And in RG's it's more that they REALLY should've made it not possible to fall off of platforms in battle, so that's more battle system than the randomization aspect.
Xenogears and PDS also share this fun trait where rotating the camera can trigger random battles.
So generally speaking I'm not bothered by random battles per se, but by stupid things triggering them, excessively high encounter rates, random battles in puzzles rooms, and random battles during platformy/climby bits.
Random or non-random, what annoys me the most with RPG combat is when fights drag on forever due to useless, non-action bits. Stuff like aTB bars that take forever to charge (Septerra Core), or really high miss rates (Wiz. 8), or high-defense enemies that can't really kill but you still have to wait forever for them to become vulnerable or just wear them down (Panzer Dragoon Saga).
I think adopting a pokemon-style "high grass" kind of thing might have wider user. Have random battles, but only in clearly-marked areas.