Yeah, so the time cone is a 4-D construction (that is itself curved in space-time). You can consider all events in the reverse cone as "observable" at a point in space-time - or vice-versa. Another thing that could happen, is that a black hole might create a shadow in a time cone, thus creating space-time events that are close, but unobservable from a given frame.
If d = (x,y,z,t) is your departure point and p = (x',y',z',t') is the destination point, then if p is in the reverse time cone (by the above definition) then paradox happens.
I hope that's more clear.
As far as Andromeda, its pretty darn close as far as these things go. What's a few million light-years between colliding galaxies? From a more philosophical physics perspective, we might ask if non-causal solutions to the Einstein equations represent real physical solutions.
Its pretty common to "throw out" non-causal solutions in E&M to great effect. Much of what we know about material science is based on that principle.
KK relations :
http://en.wikipedia.org/wiki/Kramers%E2%80%93Kronig_relations
Basically, this is a consequence of causality.
I'm, sure there are theoretical physicists that have attempted to use this basic mathematical principle in application to GR. I could imagine that might have some implications on time-travel.