Na história que eu gostaria de estar escrevendo, mas que acho que nunca sairá da minha cabeça, ocorrem muitos desses problemas. O critério que eu adoto é o seguinte:
- tratando-se da pessoa que executará a ação, depende da vivência dela. Se ela ainda não viveu a ação (mesmo que a ação seja no passado), ela executará. Mesmo que marcação do tempo indique passado, na mente dela é futuro. Analogamente, se alguém executou uma ação no futuro e depois voltou ao passado, ele já a executou (esse seria seu primeiro exemplo).
- no caso de um observador, depende da percepção dele. Usando o seu segundo exemplo, se ele sabe que o vilão pretende voltar no tempo, e ele também já descobriu qual evento no passado se refere ao crime, o vilão já cometeu o crime.
O problema desse segundo exemplo, se refere ao fato de nenhum crime ter sido identificado como sendo o do vilão em questão. Aí fica a dúvida: o crime foi cometido e ainda não foi identificado, ou o vilão desistiu (ou foi impedido, etc) e o crime nem chegou a acontecer? Nesse caso é preciso usar uma construção condicional.