Easiest way is to force an update or rebuild of your Recipient Update Service. That is the service that actually stamps the users with Exchange details etc.
ESM - Recipients, RUS, right click entry and do update.
Check properties of it as well. Might not be set for Always Run.
Neill