Generally, in Java and .net, there is no "undefined behavior". If the phonebook returns null, and the calling program forgets the check, it will inevitably throw a null reference exception when it tries to access the object the first time.
Like I said, most of the time you will get a null reference exception right after the buggy call, but not always. For example, the null entry might be passed to a function that accepts null as a parameter. My point is that the fact that you get a null reference exception is not gauranteed, and the few times that you don't can be very nasty.
If this is a multthreaded multiuser application, this option is prone to race conditions. Sooner or later, the entry will be removed by another thread between IsListed (true) and GetEntry (Exception); or it will be created between IsListed (false) and AddEntry (Exception).
We already talked about this, I would use locking in this case. I would probably do this by treating the phonebook as a resource, by implementing IDisposable so that you can use "using" to lock and unlock the phonebook like a file. Files are a good analogy, because they have the same issue (you can get FileExists (true) and still get FileOpen (Exception)). Also, if you are using it for a "multithreaded multiuser application", it sounds like you are just wanting ACID transactions. If so, I could just put the phonebook data in a database and let the database worry about most of the concurrency issues.
Anyway, all of this is getting far from my point: If I have a choice between returning null to represent an error and throwing an exception to represent an error, I will usually throw the exception.