Sending messages for processing
It looks like you only have one lock, so you can't have deadlock; but for future reference, you can add deadlock detection to the program, see for example this blog post but there are many other options available.
You may want to replace the arraylist with a ConcurrentLinkedQueue, this will let you remove the synchronized block from depositMessage and may let you remove the synchronized block from withdrawMessages and processMessages depending on how responseUpdater.sendReponse is implemented.  In general, try to use lock-free data structures when possible - they generally scale better, and you can't heave deadlock if you don't have any locks.
ConTest is a tool for detecting multithreading problems e.g. race conditions.  Java Pathfinder is a much more heavyweight approach to this.
For a large project, you may want to use a library like Akka or JMS to manage concurrency.