Adventure Island 4 (NES)
Ufouria (NES)
Blaster Master (NES)
Those are more or less Metroidvanias with backtracking and interconnected world.
Also, there're two games on the GBA called Shaman King. I think there are even more games in Japan, but the two I've played were similar to the GBA Castlevania games. I even think they're running on the same engine as Aria of Sorrow. However, while the games are similar to Castlevania, I couldn't get into either of them. The levels are connected via an overworld map, Ecclesia style, though not quite. Exploration is VERY annoying and at times downright confusing. It's hard to keep track of where you've been and where you haven't. These games should've had the classic Metroidvania map system, and skipped the overworld map altogether, IMO.
EDIT: Maybe old NES Rygar would count too?