Gnizmo on 07 December 2008
Shining Force 2 does it almost exactly like you want. Random battles can only occur when going into certain areas, but there is definatly a lot of exploring. Tactics Ogre, Final Fantasy Tactics, and FFTA/2 have it to some extent as well. The world exploring in those is pretty poor, but there are random battles.
The reason you don't see it very often is because it gets boring. Random battles can take forever in a SRPG and that really kills the flow of the game. I don't know why they don't do the exploring bit more often though. I love it in the Shining Force series.
