String note = notes.remove(0);
Чему будет равняться note? Если удаляемый элемент последний в списке, то note = null? а если не последний, то элемент с индекса 1 сместится в 0 ?
public static void removeNote(String threadName) {
            String note = notes.remove(0);
            if (note == null) {
                System.out.println("Другая нить удалила нашу заметку");
            } else if (!note.startsWith(threadName)) {
                System.out.println("Нить [" + threadName + "] удалила чужую заметку [" + note + "]");
            } else {
                System.out.println("Нить [" + threadName + "] удалила свою заметку [" + note + "]");
            }
        }