I think one of more of the five items below will help you:
#1
Exchange 2003 SP2. I am guessing that most of your clients with Outlook are configured for cache mode?
When working in cache mode you always want to manually download a new copy of the offline address book after making changes ( after a new copy is generated)
Offline Address Generation Overview
http://technet.microsoft.com/en-us/library/aa996113%28EXCHG.65%29.aspx#2
I would create to new test account user3@domain1 and user4@domain2 - just to ensure that replication and address book generation is happening as you wish.
#3
How many Exchange servers? Just one?
Now you said that external emails are bouncing as well.
Can you report the errors you get when the messages bounce?
#4
I would manually check the accounts with ldifde look at the proxy addresses.
Do this for both user1 and user2:
lfide -s dc_name -d "(dc=domain,dc=com)" -r "(samaccountname=User1)" -f out-user1-before.txt
#5
The permissions you want to keep on user1 - were they all related to AD groups, files, foldes, etc. You could remove the mailbox then remove all exchange attributes - wait until synchronization then recreate the user1 mailbox and the email addresses for that account.
HTH,
Mark