Exchange 5.5 reports error sending emails to good addresses

Exchage 5.5, about a month or so, began to report errors "email address
not found" of recipients who have good adrresses and used to receive email
from the same email server a few months ago?  Here is what I get:

The recipient name is not recognized
        The MTS-ID of the original message is: c=us;a= ;p=builderdepot
inc;l=CYBERMAIL0205270556LM6WZSLL

Another error sample:
did not reach the following recipient(s):

goodidea@xxxxxxxx on Sat, 25 May 2002 18:39:18 -0700
    Unable to deliver the message due to a communications failure
        The MTS-ID of the original message is: c=us;a= ;p=builderdepot
inc;l=CYBERMAIL0205260139LM6WZSF8

Another email sample:
psw56@hotmail on Mon, 6 May 2002 13:32:43 -0700
    Unable to deliver the message due to a communications failure
        The MTS-ID of the original message is: c=us;a= ;p=builderdepot
inc;l=CYBERMAIL0205062032GWB5X2K3
    MSEXCH:IMS:Builderdepot Inc.:BUILDERDEPOT:CYBERMAIL 3902 (000B09AA)
Host Unknown

Another email sample:
maqsood@xxxxxxxxxxxxx on Mon, 13 May 2002 10:46:52 -0700
    The recipient name is not recognized
        The MTS-ID of the original message is: c=us;a= ;p=builderdepot
inc;l=CYBERMAIL0205131618GWB5XKK2
    MSEXCH:IMS:Builderdepot Inc.:BUILDERDEPOT:CYBERMAIL 3550 (000B09AA)
550 <maqsood@xxxxxxxxxxxxx>... User unknown

Other related posts: