Turn Based Strategy with Exploration?

Some really good games match your description, most of these I've played on the ps3 but some are available on xbox360 too:

Rainbow moon(ps3):http://uk.gamespot.com/rainbow-moon/

The most recently released game in this list, and the most open-world game here too, has some interesting puzzle elements, tons of sidequests and apparantly 100+ hours of play-time, combat involves strategic thinking, controlling up to 4 characters on a small grid-based map, against up to 10 enemies, with lots of skills and different attacks available. It's kinda grind-y if you don;t buy the dlc packs though.

Blazing souls(psp):http://uk.gamespot.com/blazing-souls-accelate/

fairly recent release, you can get it on psn for the psp and it's compatible with the psvita also. HEAVY on storyline, this game is for people that like reading, gameplay involves selecting a location on the map, and then exploring that area, while it's not really open-world each location is like a small maze, with several puzzles, battles aren't as random as other games, with a gauge that ticks down with each step or action you perform in the current area, when it hits 0 you enter a battle. Battles involve moving character around a grid, attacking or using skills. What sets games by this developer apart are the way you can combine multiple "turns" into a single attack combo, providing it isn;t interrupted by enemies in the middle. this results in stupidly-long attack combos which involve (skippable) long attack animations. The game also features a monster capture system, captured monsters are treated like ordinary characters, lvling up and learning skills and can even be bred to create stronger monsers.

Cross Edge(ps3 / xbox360):http://uk.gamespot.com/cross-edge/

can;t say much about this since I never played it, based on trailers, it's simmilar to enchanted arms (below).

Enchanted Arms(ps3 / xbox360):http://uk.gamespot.com/enchanted-arms/

One of my first ps3 games, really good game but kinda short, lots of replayability though, ps3 version has a bug that prevents newgame+ from working, xbox360 has working newgame+. Gameplay involves a lot of exploration and random battles, these battles take place on 2 3x5 grids (might not be that sie, long time since I played it) each "team" (you and the enemy) has 1 side of the grid, you can move pretty much anywhere on your side, bearing in mind different skills and attack has various ranges, so positioning where you can hit the enemy and they can't hit you is the aim of movement. while there are several human characters the main party members will be "golems" think pokemon but found rather than captured. Collecting all of these golems can take 100+ hours, which makes up most of the games' post-game content, considering the strongest ones are protected by incredibly strong guardians and they usually start at lvl 1.

The Agarest series(ps3 / xbox 360):http://uk.gamespot.com/record-of-agarest-war-zero/platform/ps3/

http://uk.gamespot.com/record-of-agarest-war/platform/ps3/

http://uk.gamespot.com/record-of-agarest-war-2/

This series' individual games have the longest play-time I have ever personally seen, I put 100+ hours into the first one and was still not even close to half finishing it. I was unable to find either of the other 2 for sale anywhere (I live in the UK though, where it's hard to get hold of non-major games), the gameplay is NOT open world, but the combat is strategic and the exploration is still there, in small doses. The game focuses on the storyline and the combat over anything else, you pick locations on a map to move to, as you progress the story you move from one "node" to the next, each one usually involves a battle or story sequence (or both), upon clearing parts of the story you can return to certain explorable areas and walk around, searching for chests, other paths and more battles. I'm told the first game in the series can be completed in under 50 hours, however this would almost certainly require you to buy the dlc equipment (available through gameplay also) which is effectively some of the strongest equipment in the game baring the end-game equipment which can take a long time to obtain. The games feature a monster capture system, with breeding and sacrificing for obtaining better monsters and equipment respectively.

About following this thread: at the top there's a drop-down box that says "Favorites", click that and click "add to favorites"

There's an account option that determines how often you receive emails about the thread then (I think)

Usually forums auto-follow threads you've posted in...

Records of Agarest War 2 might be what your'e looking for.