In Exchange 2010 EMC | RECIPIENT CONFIGURATION | MAILBOX
Create New Mailbox | USER MAILBOX | EXISTING USERS | ADD
Displays some of the older AD users, but not any users that have been added in the last month (or more).
Only way to fix this is to use AD Users & Computers on the Exchange 2003 Server | Pick the Name | EXCHANGE TASKS | DELETE EMAIL ADDRESS
Once that's done, the new user will appear on Exchange Server 2010 as a selection for new mailbox.
Same thing for Contacts created in Exchange 2010. Unless I go to the Exchange 2003 Server | EXCHANGE TASKS | Create mail address, users will not receive messages for groups of which they are a member.
Hopefully this sounds familiar to someone . . . .