No email addresses being generated for new user

I was trying to add a new user on a client's SBS 2003 server today - Did all the usual stuff, set the home directory, created a roaming profile, created an exchange mailbox but even after waiting a few minutes (well ok 60 mins to be exact - over the years I've seen some servers take up to 30 mins to finish creating the exchange mailbox) I noticed that the email addresses specified in recipient update policy were not being applied to the account.

I checked everything and double checked again. So then i tried removing the mailbox from the account in ADU&C and adding it back again. Still Nothing....

I started going through everything obvious and then going through the not so obvious:

Application Log - No Errors!
System Log - No Errors!
Sophos Log (ok by this point I was getting desperate) - Still No Errors!

It was at this point that I happened to spot that the same exchange alias name existed in another account "ahhhh! that must be it!" I said to myself - feeling rather chuffed that I've solved it.......made the necessary changes and put my feet up waiting for impending success - But NO! Still nothing!

So, of course, I started Googling but didn't find much. Except a few distant entries that suggested restarting exchange services might help - "yeah right" I thought to myself. But figured I'd give it a go in the evening when everyone was off the server. So this evening I begrudgingly logged on to the Client's server, navigated to the services app then stopped and re-started all the exchange services.

And yup you've guessed it - by the time I'd opened ADU&C the flaming email addresses had been generated and everything was working perfectly!

Sometimes you know - I really hate computers!