My idea about the grandfather paradox is this:
X travels back in time and kills his grandfather. X then returns to his own time and finds it is different: nobody knows who he is, because the relevant history has been altered, from the point of his father's death onward. His grandfather would be another unsolved murder case, and X would be really stuck because no-one would know who he is or where he came from - he'd be utterly 'orphaned', for want of a better description.

That's just my theory on how it'd work. I figure that if the grandfather paradox simply cannot occur, then all time travel would be impossible. My rationale? By fulfilling the paradox, you'd be altering history. Some people would say that you're theoretically able to travel through time, provided history is not altered, by an action such as this.
However, I contend that time travel does, by its very nature, alter history. By going back to some point in the past, you're altering many things that happened: air molecules, that would have existed where your body was, have been displaced. This changes air currents that make dust motes move and fall in different places. Different air molecules would collide and react with one another, compared to which ones 'really' interacted before. For the entire duration of your visit to the past, the universe is infinitessimally heavier, meaning there is more gravitational energy. The changes are minute, but myriad. Just because a dust mote can't notice that its position has been changed, does not affect the fact that it has been affected. An intrusion into the past changes things permanently, even if it's just the destiny of a few billion atoms that is altered. If you can't eliminate your own forbear, then you shouldn't be able to venture back at all.

Edit:[q=piepants]It's like the 'there is a travelling projectile that can smash through any surface and a shield capable of blocking any projectile. If the two were to collide, what would happen?'
[/q]Ah, "an irresistible force meets an immovable object". My theory is that such a collision would release infinite energy, thereby utterly destroying the universe, down to the most fundamental level. But the theological version of the question is still an interesting one - an omnipotent God, whose act of omnipotence challenges his omnipotence... hmm.