If you want actual space, then you have to have relativity, and then any FTL travel or FTL signalling results in travelling (or sending messages) backwards in time as a practically unavoidable consequence, which means causality does not hold. :V
Its fairly easy to construct an FTL scheme in which time travel is almost impossible. Wormholes, depending on how you lay them out. Warp drive, if you don't pair them with engines capable of shifting your frame of reference significantly.
Temporary wormholes, for instance. If they appear just long enough to enable them to be used for a jump drive, and then disappear, I think it's safe. I think that's more like just taking a shortcut than FTL at that point, though. As long as you can't move the shortcut's ends through time (which is the normal problem with wormholes and relativity) there's no time travel possible.
Sergarr:
1. I tried THANCS, but there was no way to do a test battle for a ship or test anything, really. That's not really pertinent to this discussion, though.
2a. Weren't we talking about a theoretical 4x? A strategy game? You'd want calculations to predict how many turns it would take to reach a particular system. If you're using something like a hyperdrive which has acceleration and velocity in hyperspace, you could either burn as much fuel as possible to get there faster, or burn less, but either way you'd burn fuel on the way to the midpoint and then burn fuel in the opposite direction once past the midpoint. The main point is the user and AI need some way to specify how much fuel to burn or how fast they want to try to go, and that the math isn't anywhere near as straightforward as a fixed-velocity drive. (I assume you can do it with integrals or derivatives or something. #JonSnow)
2b. If it's like Master of Orion or Sword of the Stars, for example, there wouldn't really be any pathfinding. Well, except for tactical battles, I suppose. Are you thinking of something with hexes or tiles?
3. vOv
4. It shouldn't be a huge deal with a 4x (You can see what your ships are doing, and understand easily), but I remember the confusion everyone seemed to have with (the original) Frontier in the 90s, which had a newtonian flight engine. Players would tend to end up 'jousting' with enemy ships, as they'd accelerate towards them and then stop accelerating when they got close... only to fly past them at high speed because newtonian flight. Then they'd do the same thing again, and again, and again. Some people would even try to blame the AI for "flying past them repeatedly."