Segundo a documentação do Java 6 a thread acordada por um notify é escolhida arbitrariamente segundo implementação do java que você está usando, nenhuma garantia é dada se os notifys respeitam uma fila, mas é provável que isso ocorra, pelo menos no java da Sun
http://java.sun.com/javase/6/docs/api/java/lang/Object.html#notify()
Forum