I don't know whether it will fix this particular problem, but I suggest you
look at the following article:

http://support.microsoft.com/default.aspx?scid=kb;en-us;813745

However, if you decide to follow the approach it suggests (which involves
deleting a registry key and runnning Office Detect and Repair) I wonder if
you could /export/ the registry key it mentions (by selecting the key and
using File|Export). Why?
a. because it enables you to re-import the key should Detect and Repair
fail
b. because it would enable us to compare what is in our registries in that
area, which might either give a better clue as to what has been corrupted
(the article does not talk about exactly what is wrong or how it happens)
c. because if we compare keys and there is nothing significantly different,
we can probably rule out key corruption as the cause of this particular
problem in your case.

FWIW this confusing message originates from the time when Microsoft's
flagship e-mail /client/ was also called Exchange (it was the predecessor to
Outlook). It doesn't actually have anything to do with Exchange Server. To
be accurate, the message should really say that you must log onto a Mail
Profile containing your address book, but since that would be equally
mystifying to large numbers of users I don't think it would be much of an
improvement :-)

--
Peter Jamieson - Word MVP
Word MVP web site http://word.mvps.org/