The blockchain should have checkpoints every X blocks to limit the time the attacker has to act. Then if you wait 2x blocks you should be pretty safe. Blocks 1 to x are checkpointed by block x+1, which itself will be checkpointed by block 2x+1.
I think the bitcoin client already does this.