java - Make a blocking thread for message queue

Question

I'm making a simple server-client application. I'm handling the message queue this way (class MessageQueue):

private Vector<String> messages;
//Runs from any thread
public void add(String message) {
    synchronized(messages) {
      messages.add(message);
      //This is only way to unstuck messages.wait()
      messages.notifyAll();
    }
}
//Runs from special thread
private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        synchronized(messages) {
          //STUCK HERE!
          try {messages.wait();}catch(InterruptedException e) {}
          //send messages
          ...
        }
    }
}

I designed the code using this answer, but it's wrong or I haven't interpreted it correctly. Here's what happens:

1. Thread readQueue starts.
2. Thread readQueue blocks messages by synchronized block.
3. Thread readQueue blocks itself on messages.wait().
4. Another thread calls add("...") method.
5. Another thread gets stuck on synchronized block.

The messages.notifyAll() can never be called. Of course, originally, before searching, I was trying to do this:

//Runs from special thread
private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        //Wait before getting noticed of new message
        try {messages.wait();}catch(InterruptedException e) {}
        //Block messages, read them, clear them
        synchronized(messages) {
          //send messages
          ...
        }
    }
}

This throws illegal monitor exception, which forces me to put wait into synchronized - and we're just where we begun - stuck.

Answer 1

So, while noone has given me a solution I've been testing and thinking. As Kayaman has pointed out, wait call releases the variable in current synchronized block. But there is more to it.
Java is smart enough to prevent conflicts and will not release the synchronised of other operations are performed on the variable in the block.

All I had to do was putting the wait and the while that sends messages into different synchronized blocks.
This is correct code that works:

private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        //Calling isEmpty here is a little unsafe but I decided that I don't care
        if(messages.isEmpty()) {
          synchronized(messages) {
            Log.debug("Getting STUCK!");
            //After calling wait, the messages is released, just as expected
            try {messages.wait();}catch(InterruptedException e) {}
          }
        }
        //The sending
        synchronized(messages) {
          //send messages
        }
    }
}

It looks a little silly, but it makes sense. Consider the old, wrong code and a scenario:

//Runs from special thread
private void readQueue() {
    while(run) {
        synchronized(messages) {
          //STUCK HERE!
          try {messages.wait();}catch(InterruptedException e) {}
          //send messages
          ...
        }
    }
}
private void evil() {
    synchronized(messages) {
       messages.notify();
       messages.clear(); 
    }
}

1. readQueue thread enters synchronized block
2. readQueue thread calls messages.wait() and releases messages
3. Another thread runs evil()
4. Evil calls notify and allows readQueue to continue
5. At this moment, two synchronized blocks are operating on messages

I wonder how exactly is the checking implemented and what actions are allowed. I have no proof (e.g. I have found nothing about this in docs) for this but the fact that the first code works for me and the second does not.