I agree that many time travel stories do not make sense, but In all fairness to authors there are some good ones. The best ones I have seen are by Larry Niven and one by Robert Robert Heinlein.
Larry Niven has a series of short stories and one novel based on the premise that in the future the world is in a state of great poverty under a world dictatorship, in which all life except humans and their food yeast is extinct. To cater to the whims of the current Secjen (Secretary General), a time travel branch is formed to go back in time and bring ancient animals to the future. The stories make sense chronologically and handle the issue of a paradox well. Niven's stories are collected in the paperback Rainbow Mars. Niven also mentions time travel in some of his other work, through different creative methods. In the Mote in Gods Eye (I think) it is noted that a Motie had once attempted to build a time machine, but failed. I am sure others will be able to provide more Niven examples, I have not read his work in some time.
Robert Robert Heinlein's contribution is an old short story whose exact title escapes me, but i think it was "All You Zombies-". Even though the entire story is a paradox, it is one which stretches your brain and is logical once you understand it.
Another author who creatively uses time travel in a way is Orson Scott Card, who explores the effects of relativity on people and the culture shock that would follow a journey at near light speeds. In his books Enders Game, Speaker for the Dead, Xenocide, and Children of the Mind, several charecters are forced to deal with what amounts to traveling forward in time due to trips at near light speed.

Thanks to eponymous for the title to the Heinlein story