Java III Principais APis e Bibliotecas - Threads

O exercicio foi escrever as seguintes classes:

import java.util.Collection;

public class ProduzMensagens implements Runnable{

    private int comeco;
    private int fim;
    private Collection<String> mensagens;

    public ProduzMensagens(int comeco, int fim, Collection<String> mensagens){
        this.comeco=comeco;
        this.fim=fim;
        this.mensagens=mensagens;

    }

    public void setComeco(int comeco){
        this.comeco=comeco;
    }
    public int getComeco(){
        return this.comeco;
    }
    public void setFim(int fim){
        this.fim=fim;
    }
    public int getFim(){
        return this.fim;
    }

    public void run() {
        for (int i=comeco;i<fim;i++){
            synchronized(mensagens){
            System.out.println("Mensagens"+i);
        }
        }}}

import java.util.ArrayList;
import java.util.Collection;

public class RegistroMensagem {
    public static void main(String[] args) throws InterruptedException {

        Collection<String> mensagens = new ArrayList<String>();

        ProduzMensagens pm1 = new ProduzMensagens(0,10000,mensagens);
        Thread t1 = new Thread(pm1);
        t1.start();
        t1.join();

        Thread t2 = new Thread(new ProduzMensagens(10000,20000,mensagens));
        t2.start();
        t2.join();

        Thread t3 = new Thread(new ProduzMensagens(20000,30000,mensagens));
        t3.start();
        t3.join();

        System.out.println("Threads finalizadas !");

        //verifica se todas as mensagens foram guardadas
        for(int i=0;i<15000;i++){
            if(!mensagens.contains("Mensagens"+i)){
                throw new IllegalStateException("Não encotrei a mensagem " +i);
            }
        }
        //verifica se alguma mensagem ficou nula
        if(mensagens.contains(null)){
            throw new IllegalStateException("Não são permitidas mensagens nulas aqui!");
        }
        System.out.println("Fim da execução do programa");
        }

    }

Funciona quase que perfeitamente, porem mesmo após utilizar synchronized no método run, ele retorna os numeros em ordem correta, retorna o System.out "fim da execucao..." mas nao guarda a mensagem 0 como demonstra o erro abaixo, a dúvida é porque ele nao le

Exception in thread "main" java.lang.IllegalStateException: Não encotrei a mensagem 0
    at RegistroMensagem.main(RegistroMensagem.java:27)