Outlook 2003 in offline has problem with message recall

Situation description: User normally works offline and once in a while in does a manual send receive.
When someone/anyone send him an email and then does message recall, there is a notification sent back telling the original sender if the recall succeeded or failed. due to his outlook being in offline mode the message recall success/failure goes to the outbox and waits for another "send/receive". till now all is normal behavior.
Problem description: the problem (1) is that these recall success failure notification emails get stuck in the outbox. Another problem (2) is that sometimes following this set of events all emails get stuck in the outbox. another problem (3) is that emails sent emails do not reach their destinations and get message undeliverable.
Additional info:
1. windows xp
2. outlook 2003 sp2 upgrade to sp3 (hoping it would resolve problem)
3. in the past few months a new exchange server was installed (used to be exchange 2003 now it is 2007)
4. user also got a blackberry recentely.
5. in online (connect) mode none of there problems occur.