How can I tell the difference between wait(timeout) timing out and actually being notified?

You can't directly by using wait and notify, but the can use a similar construct with the Lock interface of the java.util.concurrent.locks package, with its boolean tryLock(long time, TimeUnit unit) throws InterruptedException method. true is returned if the lock was acquired and false if the waiting time elapsed before the lock was acquired.