Reply is not working for some recipients

When I'm replaying to some recipients I'm getting this error:
===============================================================================================
Delivery has failed to these recipients or distribution lists:

Metafore
There's a problem with the recipient's mailbox. Microsoft Exchange will not try to redeliver this message for you. Please try resending this message, or provide the following diagnostic text to your system administrator.


Diagnostic information for administrators:
Generating server: calgary.xxx.com

metafore@calgary.xxx.com
#< #5.2.1> #SMTP#

Original message headers:

Received: from cal-exch.xxx.com ([192.168.10.86]) by calgary-2003.xxx.com with
 Microsoft SMTPSVC(6.0.3790.3959);       Tue, 15 Jun 2010 09:41:17 -0600
Received: from kitex1.xxx.com ([192.168.10.1]) by cal-exch.xxx.com with Microsoft SMTPSVC(6.0.3790.4675);
       Tue, 15 Jun 2010 11:41:14 -0400
Received: from kitex07a.xxx.com ([192.168.10.248]) by kitex1.xxx.com with Microsoft SMTPSVC(6.0.3790.4675);
       Tue, 15 Jun 2010 11:41:11 -0400
Received: from kitex07a.xxx.com ([192.168.10.248]) by kitex07a.xxx.com
 ([192.168.10.248]) with mapi; Tue, 15 Jun 2010 11:41:11 -0400
Content-Type: application/ms-tnef; name="winmail.dat"
Content-Transfer-Encoding: binary
From: Stelian Stan <stelis@xxx.com>
To: Metafore <metafore@calgary.xxx.com>
Date: Tue, 15 Jun 2010 11:41:10 -0400
Subject: RE: teste
Thread-Topic: teste
Thread-Index: AcsMoRjX6SoIbIB/QSG2JJz0ew/tvwAABPjg
Message-ID: <4B06F3DF0345704DB275F12AC6F4ED303437655D32@kitex07a.xxx.com>
References: <677BA8F3D9B2C94ABFCE73C8688371057A2991@calgary-2003.xxx.com>
In-Reply-To: <677BA8F3D9B2C94ABFCE73C8688371057A2991@calgary-2003.xxx.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator: <4B06F3DF0345704DB275F12AC6F4ED303437655D32@kitex07a.xxx.com>
MIME-Version: 1.0
Return-Path: stelis@xxx.com
X-OriginalArrivalTime: 15 Jun 2010 15:41:11.0964 (UTC) FILETIME=[2E809DC0:01CB0CA1]
===============================================================================================

I already try this:

Delete the Outlook clients nickname cache file.
Changed the Outlook to non-cached mode to ensure it is not a cached entry from the Offline Address Book.
Still not working.

Any suggestions?